SageMath 关于 Paviller 加密系统的 Zn 和 Znn 转换问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3214 天前的主题，其中的信息可能已经有所发展或是发生改变。

代码我直接粘贴上来了，放在最后。

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

4 条回复 • 2016-02-04 04:06:46 +08:00

oIMOo

2016-02-03 03:10:02 +08:00

为咩不能编辑了……
Zn 数学的表达是 Z/nZ
Zn^2 数学的表达是 Z/n^2Z

oIMOo

2016-02-03 16:32:39 +08:00

自己顶一下……

oIMOo

2016-02-03 19:44:30 +08:00

已解决：
完成版代码见维护末尾。
此代码为了节省运算，将 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

oIMOo

2016-02-04 04:06:46 +08:00

以下的（ 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