AMM算法(Adleman-Manders-Miller算法)可以追溯到1977年,当时Leonard Adleman、Eric Manders和G.L. Miller首次提出了这个求解二次剩余的方法。然而,原始的AMM算法主要关注于二次剩余问题,并且在尝试将其推广到一般的高次剩余问题时遇到了困难,因为推广过程中会产生新的障碍。
在AMM算法的基础上,后来的研究者们进行了进一步的探索和改进。例如,在2006年,Paulo S. L. M. Barreto和Benjamin Voloch提出了一个针对有限域F_q^m上的r次剩余求解问题的新算法(简称BV算法)。这个算法在特定条件下(如r整除q-1且(m,r)=1)具有较低的复杂度。
在AMM算法的历史中,值得注意的是它在密码学和数论领域的应用。由于AMM算法可以用于求解二次剩余问题,它在公钥密码学、数字签名等领域有着广泛的应用。例如,RSA公钥密码系统就依赖于求解大整数的模平方根问题,而AMM算法或其改进版本可以用于加速这一过程的计算。
总的来说,AMM算法(包括原始的Adleman-Manders-Miller算法及其后续改进版本)在密码学、数论和计算机科学等领域都有着重要的历史和应用。随着技术的不断发展,AMM算法及其相关技术将继续在这些领域中发挥重要作用。
在CTF比赛中,AMM主要是为了解决RSA解密中e与phi都不互素的问题,一般的方法是将m^gcd看作m然后求出m^gcd,再开根号得到m,但当e与p-1、q-1都不互素的时候,用上面的方法最后变成了将m^e看作m,也就是说e被约为了1,这显然是解不了的,所以有了AMM算法,他使我们能够在有限域内开根号(可以简单的理解为在模p的情况下开根号),我们通过分别在模p、q下开e次方分别得到模p、q下的m,再用中国剩余定理CRT求m,接下来简单介绍一下相关的算法原理。
1、AMM开2次方(解决二次剩余问题)
AMM算法最初是为了解决二次剩余问题而设计的,其核心思想是通过迭代计算算术平均数和几何平均数来逼近一个特定的值。在二次方的情境下,这个值通常是一个数的平方根。所以我们先从最简单的开二次方来了解,然后通过二次方来推广到高次方。(补充一下,下面的p都默认为奇素数)
首先对于二次方式子我们有:
式子中p为素数,此时我们可以将p-1写成2^t*s的形式并且s为奇数。(就是将p-1里所有的2都提出来)
由欧拉准则(注意这里是准则不是定理,如果不知道可以去了解一下):
对二次剩余x
对二次非剩余y:
1-1、当t=1时
如果t=1,此时t-1=0,(p-1)/2=s,二次剩余:
两边同乘x,然后开根号得:
现在将c代入可以得到:
又有:
于是就能得到m。
上面的就是可以说就是AMM算法的精髓,大概步骤就是:
- 将p-1变成2^t*s的形式。
- 在想办法将t消掉。
- 然后两边乘x再开根号
后面开高次方也是同样的道理,比较麻烦的是消掉t。
举个栗子:
7为明文,11为密文
如果是二次非剩余则为-x(1/2)不能用来求出m,所以不会拿来用,你可能会疑惑没用为什么写,在后面会有它的用处。
1-2、当t>=2时
即p-1有两个以上的2时,这时想消掉t就要用点技巧了,我们的第一反应当然是开平方。
开方后会有两种结果,我们前面说了我们不需要负根(或者叫二次非剩余),所以我们给负根配上一个非二次剩余y(随便自己找一个)
这里的k是为了控制是否引入非二次剩余项,我们开出正时根k=0,开出负根时k=1,之后不断对x开根,一直到2的指数为0,一共t-1个k:
此时两边同时乘x再开根号得到:
和t=1一样将c代入就能求出明文:
开二次方的算法脚本如下:
import random
def AMM2(residue,p):
# 计算t,s
t = 0
s = p - 1
while s % 2 == 0:
t += 1
s = s // 2
#当t=1时
if t==1:
return pow(residue,(s+1)//2,p)
#生成非二次剩余时,回炉重造
noresidue=random.randint(1,p)
while pow(noresidue,(p-1)//2,p)==1:
noresidue = random.randint(1,p)
h=1
a=pow(noresidue,s,p)
b=pow(residue,s,p)
#消掉t
for i in range(1,t):
e=2**(t-1-i)
d=pow(b,e,p)
if d==1:
k=0
else:
k=1
b=b * pow(a, 2*k, p)%p
h=pow(a,k,p)*h%p
a=pow(a,2,p)
return h*pow(residue,(s+1)//2,p)%p
1-3、由AMM得到的一个解求另一个解
我们在开平方的时候都知道一般都有两个解x和-x,所以在有限域中很简单的就用p-x就能得到另一个解,但是我们讲e=2的情况是为了引入e>2时开高次方,所以还是讲一下原理
首先我们在前面已经得到了一个根记为m0,已知
由费马小定理可以得到:
于是得到了两不同的解res1=m0、res2=m0*X^((p-1)/2)%p(X为有限域里的数)。
def find(p):
#随便取a然后计算另一个解,如果不为p那说明找到了另一个解
root=[]
while len(root)<2:
a=random.randint(2,p-1)
res=pow(a,(p-1)//2,p)
if res not in root:
root.append(res)
return root
完整代码:
import random
def find(p):
root=[]
while len(root)<2:
a=random.randint(2,p-1)
res=pow(a,(p-1)//2,p)
if res not in root:
root.append(res)
return root
def AMM2(residue,p):
t = 0
s = p - 1
while s % 2 == 0:
t += 1
s = s // 2
if t==1:
return pow(residue,(s+1)//2,p)
noresidue=random.randint(1,p)
while pow(noresidue,(p-1)//2,p)==1:
noresidue = random.randint(1,p)
h=1
a=pow(noresidue,s,p)
b=pow(residue,s,p)
for i in range(1,t):
e=2**(t-1-i)
d=pow(b,e,p)
if d==1:
k=0
else:
k=1
b=b * pow(a, 2*k, p)%p
h=pow(a,k,p)*h%p
a=pow(a,2,p)
return h*pow(residue,(s+1)//2,p)%p
上面的是指数e为2的情况下AMM算法的算法原理,也是最初求有限域二次方根算法,我们通过最简单的情况来引入AMM算法,后面当e大于2时的情况也类似。
2、AMM开高次方
同样的,对于多次方式子我们有:
这里先要可以分两组情况来考虑:
2-1、gcd(e,p-1)=1
这种就是最简单的RSA,不过赘述。
2-2、e|p-1
和上面一样,先令$p-1=e^t*s$,就是将2改为了e
再同样由费马小定理:
我们从p-1中提一个e出来
现在找一个最小的非负整数d,使s|ed-1,可以认为d就是模s下r的逆元,有ed-1=ks(k为常数)
有ed-1=ks,就相当于两边同时k次方,所以模p后的结果仍然为1:
就像上面一样,我们要考虑两种情况
2-2-1、当t=1时
此时e^(t-1)=1,于是上式就等于
两边同时乘c,得到
所以c^d为c在模p下的一个e次根,这里相当于上面乘x后再开根号一样。
2-2-2、当t>=2时
同样像上面一样先想到开e次方,但注意取e次非剩余q时,因为不是2次方根,所以非剩余不是-1,而是:
我们可以定义一个生成元为q的模p的循环群G
在该循环群G中,我们现在定义:
所以可以得到一个生成元为$K_1=q^{{p-1}\over e}$为的G的·子群K:
在这个子群里,所有的元素都是由$K_1=q^{{p-1}\over e}$生成的,所以所有元素的e次方都为1,因为子群K里正好有e个元素,所以K是模1开r次方根的结果的集合。
对于群来说每个元素都存在逆元,而且由于$q^{p-1}\equiv 1(modp)$,所以对于子群里如何一个元素$q^{{p-1}\over e}$,都有:
所以:
有了这两个条件,我们可以开始像解平方根那样解n次方根了:
首先
上式在前面有写,忘了可以看看(2-2、r|p-1下面)
开e次方后余数为集合K中的一个数,设为$K_{e-j}$,即:(虽然上面是从余1进行e次方来的,但开了e次方会有很多解):
两边同乘逆元$K_j$,得:
即:
继续开方得到:
然后再乘c在所有项提e次方:
再开e次方得到:
然后得到了解
脚本:
import math
import gmpy2
import random
def AMM(residue,e,p):
# 计算t,s
t = 0
s = p - 1
while s % e == 0:
t += 1
s = s // e
#用求逆元计算d
d=gmpy2.invert(e,s)
#当t=1时的情况
if t==1:
return pow(residue,d,p)
#t>=2的情况
#计算一个e次非剩余
noresidue = random.randint(1, p)
while pow(noresidue, (p - 1) // e, p) == 1:
noresidue = random.randint(1, p)
a=pow( noresidue , ( e ** ( t-1 )) * s, p )
b=pow( residue , e * d - 1, p )
c=pow( noresidue , s , p )
h=1
for i in range(1,t):
d=pow( b , e** ( t-1-i ) , p )
if d==1:
j=0
else:
j=-math.log(d,a)
b=pow( pow ( c , e , p ) , j , p ) * b % p
h=pow( c , j , p ) * h % p
c=pow( c , e , p )
return pow( residue , d , p ) * h % p
2-3、由AMM得到的一个解求其他解
对于:
当r|p-1,会有e个单位根(翻译一下,在模p下e个e次方根),当e不能整除p-1时,只有一个单位根,即1本身。
从一个根得到其他根的思路为:首先找到r个不同的单位根,然后让(AMM得到的根)*单位根%q。
上面的x是随机的并且是在p以内的正整数,因此$x^{q-1\over e}$是r次单位根,只要找到r个不同的单位根就可以了。
完整代码:
import random
import math
import gmpy2
def find(e,p):
root = []
while len(root) < e:
a = random.randint(2, p - 1)
res = pow(a, (p - 1) // e, p)
if res not in root:
root.append(res)
return root
def AMM(residue,e,p):
# 计算t,s
t = 0
s = p - 1
while s % e == 0:
t += 1
s = s // e
d=gmpy2.invert(e,s)
if t==1:
return pow(residue,d,p)
noresidue = random.randint(1, p)
while pow(noresidue, (p - 1) // e, p) == 1:
noresidue = random.randint(1, p)
a=pow( noresidue , ( e ** ( t-1 )) * s, p )
b=pow( residue , e * d - 1, p )
c=pow( noresidue , s , p )
h=1
for i in range(1,t):
d=pow( b , e** ( t-1-i ) , p )
if d==1:
j=0
else:
j=-math.log(d,a)
b=pow( pow ( c , e , p ) , j , p ) * b % p
h=pow( c , j , p ) * h % p
c=pow( c , e , p )
return pow( residue , d , p ) * h % p
residue = 24
e = 5
p = 131
if (p-1)%e==0:
mp = AMM(residue, e, p)
print("AMM得到的一个根为:",mp)
root_list = find(e, p)
for i in range(len(root_list)):
a = mp * root_list[i] % p
print("第{}个根:{}".format(i + 1, a))
else:
print("e不能整除(p-1),AMM不适用")
3、结合中国剩余定理求解
将模p和模q下求得的所有解通过爆破的方式求出所有解,然后在筛选出要的
import random
import math
import gmpy2
def find(e, p):
root = []
while len(root) < e:
a = random.randint(2, p - 1)
res = pow(a, (p - 1) // e, p)
if res not in root:
root.append(res)
return root
def AMM(residue, e, p):
# 计算t,s
t = 0
s = p - 1
while s % e == 0:
t += 1
s = s // e
d = gmpy2.invert(e, s)
if t == 1:
return pow(residue, d, p)
noresidue = random.randint(1, p)
while pow(noresidue, (p - 1) // e, p) == 1:
noresidue = random.randint(1, p)
a = pow(noresidue, (e ** (t - 1)) * s, p)
b = pow(residue, e * d - 1, p)
c = pow(noresidue, s, p)
h = 1
for i in range(1, t):
d = pow(b, e ** (t - 1 - i), p)
if d == 1:
j = 0
else:
j = -math.log(d, a)
b = pow(pow(c, e, p), j, p) * b % p
h = pow(c, j, p) * h % p
c = pow(c, e, p)
return pow(residue, d, p) * h % p
#中国剩余定理脚本,m_list为余数,a_list为除数
def Get_Mi(m_list, m):
M_list = []
for mi in m_list:
M_list.append(m // mi)
return M_list
def Get_resMi(M_list, m_list):
resM_list = []
for i in range(len(M_list)):
resM_list.append(Get_ni(M_list[i], m_list[i])[0])
return resM_list
def Get_ni(a, b):
if b == 0:
x = 1
y = 0
q = a
return x, y, q
ret = Get_ni(b, a % b)
x = ret[0]
y = ret[1]
q = ret[2]
temp = x
x = y
y = temp - a // b * y
return x, y, q
def result(a_list, m_list):
for i in range(len(m_list)):
for j in range(i + 1, len(m_list)):
if 1 != math.gcd(m_list[i], m_list[j]):
print("不能直接利用中国剩余定理")
return
m = 1
for mi in m_list:
m *= mi
Mi_list = Get_Mi(m_list, m)
Mi_inverse = Get_resMi(Mi_list, m_list)
x = 0
for i in range(len(a_list)):
x += Mi_list[i] * Mi_inverse[i] * a_list[i]
x %= m
return x
def RSA_dec(n,e,c):
phi=n-1
gcd1 = gmpy2.gcd(e, phi)
t1 = e // gcd1
dt = gmpy2.invert(t1, phi)
m_gcd1 = gmpy2.powmod(c, dt, n)
m = gmpy2.iroot(m_gcd1, gcd1)[0]
return m
#m=197
c = 22487
e = 5
p = 131
q=181
lp = []
if (p - 1) % e == 0:
mp = AMM(c, e, p)
root_list = find(e, p)
for i in range(len(root_list)):
a = mp * root_list[i] % p
lp.append(int(a))
lq=[]
if (q - 1) % e == 0:
mq = AMM(c, e, q)
root_list = find(e, q)
for i in range(len(root_list)):
a = mq * root_list[i] % q
lq.append(int(a))
clis=[p,q]
ylis=[0,0]
for i in lp:
for j in lq:
ylis[0]=i
ylis[1]=j
print(result(ylis,clis))
上面提到的中国剩余定理定理,就是通过一个数除以多个数得到多个余数,根据除数和余数得到原本的数,如果不懂的可以去了解一下。