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 randomdef 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 ）% pprint（amm2（4，7））
最佳化：
import randomdef 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 ）% pprint（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 py^（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 randomimport mathimport libnumimport timefrom Crypto。Util。number import bytes_to_long，long_to_bytesp = 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）） % pprint（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 randomimport mathimport libnumimport timefrom Crypto。Util。number import bytes_to_long，long_to_bytesp = 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 rootsdef check（m）： if ‘flag’ in m： print（m） return True else： return False e = 1801c = 821562155714228494350968286343241874202753771452745916900616612053610190986294297934462409534126095213198464996196364868528238538372119009517541428785632007137206972918081643841690069171088425923887930051635578719252415693144672179185417101210954906623326286804995637775062840407550493095027500638719998p = 19897846550210846565807788524492364050901480736489979129040638436463635149815428186161001280958415730930156556581274966745574164608778242980049611665461488306439665507971670397595035647317930606555771720849158745264269952668944940061576328219674721623208805067371087817766416300084129945316973502412996143mps = AMM（c，e，p）for mpp in mps： solution = str（long_to_bytes（mpp）） if check（solution）： print（solution）
最後美觀一點的數學公式
本文由
Ph0en1x
原創釋出
轉載，請參考轉載宣告，註明出處： https：//www。anquanke。com/post/id/262634
安全客 - 有思想的安全新媒體
