V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
oIMOo
V2EX  ›  数学

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

  •  
  •   oIMOo · 2016-02-03 02:57:37 +08:00 · 3624 次点击
    这是一个创建于 3222 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    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
        1
    oIMOo  
    OP
       2016-02-03 03:10:02 +08:00
    为咩不能编辑了……
    Zn 数学的表达是 Z/nZ
    Zn^2 数学的表达是 Z/n^2Z
    oIMOo
        2
    oIMOo  
    OP
       2016-02-03 16:32:39 +08:00
    自己顶一下……
    oIMOo
        3
    oIMOo  
    OP
       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
        4
    oIMOo  
    OP
       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
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1188 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 18:30 · PVG 02:30 · LAX 10:30 · JFK 13:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.