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)
最后美观一点的数学公式
还没有评论，来说两句吧...