这是一个创建于 3607 天前的主题，其中的信息可能已经有所展或是发生改变。
代码我直接粘贴上来了，放在最后。
Decoding 所用公示：
L( u ) = ( u - 1 ) / n
m = D( c ) ≡ ( L( c^( λ( n )) ( mod n^2 ))) / ( L( g^( λ( n )) ( mod n^2 ))) (mod n)
问题在于：
在 m 中，被除数和除数都是属于 Znn ，也就是属于 Integers(n^2)
后面 modulo n 范围自然就成了 Zn
这里就会出现 inverse dose not existe
如何顺利转换 Znn 到 Zn 呢？
def getRandom (): tmp = 0; while (tmp == 0): r = ZZ.random_element(2^(512 - 1), 2^512) # random number 512 bits from 2^(512 - 1) to 2^215 - 1 if is_prime(r): tmp = 1 return r def getKeyList (): LKey = [] # initialize prime number p and q p = getRandom() q = getRandom() while (p == q): p = getRandom() LKey.append(p) #Lkey[0] LKey.append(q) #Lkey[1] lambdan = lcm(p - 1, q - 1) LKey.append(lambdan) #Lkey[2] n = p * q LKey.append(n) #Lkey[3] if (gcd(n, lambdan) != 1): return false g = n + 1 LKey.append(g) #Lkey[4] # how it works with return listKey1, listKey2 ? return LKey def getPubKey (LKey): KPub = [] KPub.extend(LKey[3:5]) return KPub def getPriKey (LKey): KPri = [] KPri.extend(LKey[0:3]) return KPri def Encoding (m, KPub): n = KPub[0] Zn = Integers(n) Znn = Integers(n^2) g = Znn(KPub[1]) r = Znn(abs(ZZ.random_element())) c = Znn(g^m * r^n) return c def L(u, KPub): n = KPub[0] Zn = Integers(n) Znn = Integers(n^2) return Zn((u - 1)/n) def Decoding (c, KPub, KPri): n = KPub[0] Zn = Integers(n) Znn = Integers(n^2) g = Znn(KPub[1]) lambdan = Znn(KPri[2]) Pup = L(pow(c, lambdan, n^2), KPub) Pdown = L(pow(g, lambdan, n^2), KPub) m = Zn(Pup / Pdown) # bug here #up = pow(c, lambdan, n^2) - 1 #down = pow(g, lambdan, n^2) - 1 #m = Zn(up / down) # bug here return m  | 1 oIMOo OP 为咩不能编辑了…… Zn 数学的表达是 Z/nZ Zn^2 数学的表达是 Z/n^2Z |
| 2 oIMOo OP 自己顶一下…… |
| 3 oIMOo OP 已解决： 完成版代码见维护末尾。 此代码为了节省运算，将 g 定义为 g = 1 + n 。 （新问题来了： mac 怎么打 “ ` ”，如果用 1 键左边的，我打出来是“ ”） ```python def getRandom (): tmp = 0; while (tmp == 0): r = ZZ.random_element(2^(512 - 1), 2^512) # random number 512 bits from 2^(512 - 1) to 2^215 - 1 if is_prime(r): tmp = 1 return r def getKeyList (): LKey = [] # initialize prime number p and q p = getRandom() q = getRandom() while (p == q): p = getRandom() LKey.append(p) #Lkey[0] LKey.append(q) #Lkey[1] lambdan = lcm(p - 1, q - 1) LKey.append(lambdan) #Lkey[2] n = p * q LKey.append(n) #Lkey[3] if (gcd(n, lambdan) != 1): return false g = n + 1 LKey.append(g) #Lkey[4] # how it works with return listKey1, listKey2 ? return LKey def getPubKey (LKey): KPub = [] KPub.extend(LKey[3:5]) return KPub def getPriKey (LKey): KPri = [] KPri.extend(LKey[0:3]) return KPri def Encoding (m, KPub): n = KPub[0] Zn = Integers(n) Znn = Integers(n^2) g = Znn(KPub[1]) r = Znn(abs(ZZ.random_element())) c = Znn(g^m * r^n) return c def L(u, KPub): n = KPub[0] Zn = Integers(n) Znn = Integers(n^2) return Zn((u - 1).lift() / n) def Decoding (c, KPub, KPri): n = KPub[0] Zn = Integers(n) Znn = Integers(n^2) g = Znn(KPub[1]) lambdan = Znn(KPri[2]) Pup = L(pow(c, lambdan, n^2), KPub) Pdown = L(pow(g, lambdan, n^2), KPub) m = Zn(Pup / Pdown) return m |
| 4 oIMOo OP 以下的 （ may be ） 是最终版本： # Paviller CryptoSystem on SageMath # Feb. 03, 2016 def getRandom (): tmp = 0; while (tmp == 0): r = ZZ.random_element(2^(512 - 1), 2^512) # random number 512 bits from 2^(512 - 1) to 2^215 - 1 if is_prime(r): tmp = 1 return r def getKeyList (): LKey = [] # initialize prime number p and q p = getRandom() q = getRandom() while (p == q): p = getRandom() LKey.append(p) #Lkey[0] LKey.append(q) #Lkey[1] lambdan = lcm(p - 1, q - 1) LKey.append(lambdan) #Lkey[2] n = p * q LKey.append(n) #Lkey[3] if (gcd(n, lambdan) != 1): return false g = n + 1 LKey.append(g) #Lkey[4] # how it works for returning listKey1 & listKey2 at the same time? return LKey def getPubKey (LKey): KPub = [] KPub.extend(LKey[3:5]) print("Public Keys: n and g") return KPub def getPriKey (LKey): KPri = [] KPri.extend(LKey[0:3]) print("Private Keys: p, q and lamdba(n)") return KPri def Encoding (m, KPub): n = KPub[0] Zn = Integers(n) Znn = Integers(n^2) g = Znn(KPub[1]) r = 0 while (r == 0): # r non-null r = Znn((Zn.random_element())) c = Znn(g^m * r^n) return c def L(u, KPub): n = KPub[0] Znn = Integers(n^2) return ((Znn(u).lift() - 1) / n) def Decoding (c, KPub, KPri): n = KPub[0] Zn = Integers(n) Znn = Integers(n^2) g = Znn(KPub[1]) lambdan = Znn(KPri[2]) Pup = L((c^lambdan), KPub) Pdown = L((g^lambdan), KPub) m = Zn(Pup / Pdown) return m # fast test with: # m = getRandom(); m # a number as clear message # LKey = getKeyList(); KPub = getPubKey (LKey); KPri = getPriKey (LKey); c = Encoding (m, KPub); Decoding (c, KPub, KPri) 放在 GitHub 了： https://github.com/MrBowen/Paviller-on-SageMath.git |
Select Language