RSA中e和phi不互素时的AMM开根

阅读量    183342 |

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

AMM

2021闽盾杯遇到的题,赛后听大佬们说要用AMM算法。
于是先百度了一波,发现网上的代码多多少少都有bug,而且跑很久。
只好自己读paper并且写下些许心得。
最终实现的代码跑出该题只用了几秒钟吧(本人才疏学浅按照自己的理解解的)。
若大佬们觉得哪里不妥还望斧正。

m^e = c   mod  p

p在已知e下易分解得到s

p-1 = e^t * s

 

首先开二次方

即 e = 2

欧拉准则:
二次剩余x :x^((p-1) / 2) = (x^s)^e^(t-1) = 1 mod p


x^((p-1) / 2) 
= (x^s)^(2^(t-1))
= 1   mod  p

二次非剩余y :y^((p-1) / 2) = (y^s)^e^(t-1) = -1 mod p


y^((p-1) / 2) 
= (y^s)^(2^(t-1))
= -1   mod  p

若t = 1:

对于二次剩余的式子:

(x^s)^(2^(t-1)) = 1  mod p

同时乘上x,并开方

x^((s+1)/2) = x ^ (1/2) mod p

带入:c

c ^ ((s+1)/2) = m  mod p

开方结果即为:

c ^ ((s+1)/2)

若t >= 2:

(x^s)^(2^(t-1)) = 1  mod p

对上式开根,有两种结果

(x^s)^(2^(t-1)) = 1  mod p
(x^s)^(2^(t-2)) = 1  mod p
(x^s)^(2^(t-2)) = -1  mod p

我们不需要负根,所以我们配上一个非二次剩余

(x^s)^(2^(t-2)) = -1  mod p
(y^s)^(2^(t-1)) = -1  mod p
(x^s)^(2^(t-2)) * (y^s)^(2^(t-1)*k) = 1  mod p

当开出负根k=1,开出正根k=0

(x^s)^(2^(t-i))  mod p

取决于上面这个值

接下来重复上述操作,直到不能开二次方即2的指数为0

总计t-1个k

x ^ s * (y^s)^(k_1+2 * k_2+...+2^(t-3) * k_(t-1)) =  1  mod p

然后乘上二次剩余x两边取平方。

x ^ ((s+1)/2) * (y^s)^(k_1+2 * k_2 +...+2^(t-3) * k_(t-1)) = x^(1/2)  mod p

算法:

import random
def amm2(x,p):
    #开二次方的代码
    #示例:2^2 = 4 mod 7  7-1 = 2 * 3 
    # 4 ^((3+1)/2) mod 7 = 2
    y = random.randint(1, p) 
    #生成二次非剩余
    while y ** ((p-1) // 2) == 1:
        y = random.randint(1, p)
    #计算t s 
    t = 1
    s = 0
    while p % 2 == 0:
        t += 1
    s = p // (2**t)
    #计算a = y^s b = x^s h =1
    #h为二次非剩余部分的积
    a = y**s
    b = x**s
    h = 1
    #
    for i in range(1,t):
        tmp = 2**(t - 1 - i)
        d = b**tmp
        if d == 1 :
            k = 0
        else:
            k = 1
        b = b * ((a**2)**k)
        h = h * a**k
        a = a**2
    print(h)
    print(s)
    print((s + 1) // 2)
    return (x**((s + 1) // 2) * h )% p

print(amm2(4,7))

优化:

import random
def amm2(x,p):
    #开二次方的代码
    #示例:2^2 = 4 mod 7  7-1 = 2 * 3 
    # 4 ^((3+1)/2) mod 7 = 2
    y = random.randint(1, p) 
    #生成二次非剩余
    #while y ** ((p-1) // 2) == 1:
    while pow(y, ((p-1) // 2), p) == 1:
        y = random.randint(1, p)
    #计算t s 
    t = 1
    s = 0
    while p % 2 == 0:
        t += 1
    s = p // (2**t)
    #计算a = y^s b = x^s h =1
    #h为二次非剩余部分的积
    a = pow(y, s, p)
    b = pow(x, s, p)
    h = 1
    #判断k值
    for i in range(1,t):
        tmp = 2**(t - 1 - i)
        d = pow(b, tmp, p)
        if d == 1 :
            k = 0
        else:
            k = 1
        b = b * pow(pow(a, 2, p), k, p)
        h = h * pow(a, k, p)
        a = pow(a, 2, p)
    return (pow(x,((s + 1) // 2),p) * h )% p
print(amm2(4,7))

开e次方根

原理:

我们知道 m^e = c mod p肯定有解

e次剩余 x等同c

费马小定理

a ^ (p-1) = 1  mod p

x^((p-1) / e) 
= (x^s)^(e^(t-1))
= 1   mod  p

e次非剩余


y^((p-1) / e) = (y^s)^(e^(t-1))= ?   mod  p

考虑开e次方

类别开二次方我们需要 对下面开e次方

x^(s+1)

故需要找到一个值alpha使得:

e*alpha -1 = k*s

对e次剩余扩展从s扩展到ks

(x^(k*s))^(e^(t-1)) = 1   mod p
(x^(e*alpha -1 ))^(e^(t-1)) = 1   mod p

同理:不断对剩余开e次,但是现在开e次有e种选择

即 1 的r次根

(1,y_1,...,y_(e-1))

我们已知该类元素的e次方都为1,以及费马小定理

(y_e) ^ e = 1  mod p
y^(p-1) = 1  mod p

不妨直接构造非二次剩余y的循环群

(y_0,...y_(e-1))
{1,(y^((p-1)/e))^1,(y^((p-1)/e))^2,...,(y^((p-1)/e))^(e-1)}
((y^s)^(e^(t-1))) ^i

而且对于i>=1有以下结论

y_i * y_(e-i) = 1

故只要在每次开e次方的时候补上y即可

(x^(e*alpha -1 ))*(y^s)^(k_1+2 * k_2 +...+2^(t-3) * k_(t-1)) = 1   mod p

同二次k值的获取来自开e次方的结果:

(x^s)^(2^(t-i))  mod p

对上面的值关于y取log即可得到是循环群里的第几个元素再取逆mod e

最后一步两边乘上x开e次根

(x^(e*alpha -1 ))*(y^s)^(k_1+2 * k_2 +...+2^(t-3) * k_(t-1)) * x = x   mod p
(x^(alpha -1 +1))*(y^s)^(k_1+2 * k_2 +...+2^(t-3) * k_(t-1)) = x^(1/e)  mod p
(x^(alpha))*(y^s)^(k_1+2 * k_2 +...+2^(t-3) * k_(t-1)) = x^(1/e)  mod p

算法:

import random
import math
import libnum
import time
from Crypto.Util.number import bytes_to_long,long_to_bytes
p = 0
#设置模数
def GF(a):
    global p
    p = a
#乘法取模
def g(a,b):
    global p
    return pow(a,b,p)


def AMM(x,e,p):
    GF(p)
    y = random.randint(1, p-1)
    while g(y, (p-1)//e) == 1:
        y = random.randint(1, p-1)
        print(y)
    print("find")
    #p-1 = e^t*s
    t = 1
    s = 0
    while p % e == 0:
        t += 1
        print(t)
    s = p // (e**t)
    print('e',e)
    print('p',p)
    print('s',s)
    print('t',t)
    # s|ralpha-1
    k = 1    
    while((s * k + 1) % e != 0):
        k += 1
    alpha = (s * k + 1) // e
    #计算a = y^s b = x^s h =1
    #h为e次非剩余部分的积
    a = g(y, (e ** (t - 1) ) * s)
    b = g(x, e * alpha - 1)
    c = g(y, s)
    h = 1
    #
    for i in range(1, t-1):
        d = g(b,e**(t-1-i))
        if d == 1:
            j = 0
        else:
            j = (-math.log(d,a) % e)
        b = b * (g(g(c, e), j))
        h = h * g(c, j)
        c = g(c,e)
    return (g(x,alpha * h)) % p
print(AMM(4,2,7))

 

求所有的根

我们已知1的e个根

(y_0,...y_(e-1))
{1,(y^((p-1)/e))^1,(y^((p-1)/e))^2,...,(y^((p-1)/e))^(e-1)}
((y^s)^(e^(t-1))) ^i

我们只要用所求的根去乘上这e个元素的值再取模就能得到结果了

 

例题:2021黑盾杯Cryptoy1

题目:

另外给了个png图片,lsbR层隐写了培根加密的英文e,解码出e = 1801

对e在p-1下求逆失败,发现p-1是e的倍数,利用AMM算法开根号求解

import random
import math
import libnum
import time
from Crypto.Util.number import bytes_to_long,long_to_bytes
p = 0
#设置模数
def GF(a):
    global p
    p = a
#乘法取模
def g(a,b):
    global p
    return pow(a,b,p)


def AMM(x,e,p):
    GF(p)
    y = random.randint(1, p-1)
    while g(y, (p-1)//e) == 1:
        y = random.randint(1, p-1)
        print(y)
    print("find")
    #p-1 = e^t*s
    t = 1
    s = 0
    while p % e == 0:
        t += 1
        print(t)
    s = p // (e**t)
    print('e',e)
    print('p',p)
    print('s',s)
    print('t',t)
    # s|ralpha-1
    k = 1    
    while((s * k + 1) % e != 0):
        k += 1
    alpha = (s * k + 1) // e
    #计算a = y^s b = x^s h =1
    #h为e次非剩余部分的积
    a = g(y, (e ** (t - 1) ) * s)
    b = g(x, e * alpha - 1)
    c = g(y, s)
    h = 1
    #
    for i in range(1, t-1):
        d = g(b,e**(t-1-i))
        if d == 1:
            j = 0
        else:
            j = -math.log(d,a)
        b = b * (g(g(c, e), j))
        h = h * g(c, j)
        c = g(c, e)
    #return (g(x, alpha * h)) % p
    root = (g(x, alpha * h)) % p
    roots = set()
    for i in range(e):
        mp2 = root * g(a,i) %p
        assert(g(mp2, e) == x)
        roots.add(mp2)
    return roots
def check(m):
    if 'flag' in m:
        print(m)
        return True
    else:
        return False

    e = 1801
c = 821562155714228494350968286343241874202753771452745916900616612053610190986294297934462409534126095213198464996196364868528238538372119009517541428785632007137206972918081643841690069171088425923887930051635578719252415693144672179185417101210954906623326286804995637775062840407550493095027500638719998
p = 19897846550210846565807788524492364050901480736489979129040638436463635149815428186161001280958415730930156556581274966745574164608778242980049611665461488306439665507971670397595035647317930606555771720849158745264269952668944940061576328219674721623208805067371087817766416300084129945316973502412996143
mps = AMM(c,e,p)
for mpp in mps:
        solution = str(long_to_bytes(mpp))
        if check(solution):
           print(solution)

 

最后美观一点的数学公式

分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多