扩大节-合并节-数据目录

费马小定理，之前粗略的学习过，但不是很熟练，也不太会用，只是说看到别人的wp里有用到不至于看不懂吧，自己也经常忘记，所以记录一下，加深印象，并且便于自己复习。

内容

若存在互质的两整数a、p，满足gcd(a,p)==1，则有：$a^{p-1}\equiv 1(modp)$，两边同乘a便得到：$a^{p}\equiv a(mod p)$

下面举两个例子，遇到的运用费马小定理的题。

little little fermat

题目：

from Crypto.Util.number import *
from random import *
from libnum import *
import gmpy2
from secret import x
 
flag = b'?????????'
m = bytes_to_long(flag)
def obfuscate(p, k):
    nbit = p.bit_length()
    while True:
        l1 = [getRandomRange(-1, 1) for _ in '_' * k]
        l2 = [getRandomRange(100, nbit) for _ in '_' * k]
        l3 = [getRandomRange(10, nbit//4) for _ in '_' * k]
        l4 = [getRandomRange(2, 6) for _ in '_' *k]
        A = sum([l1[_] * 2 ** ((l2[_]+l3[_])//l4[_]) for _ in range(0, k)])
        q = p + A
        if isPrime(q) * A != 0:
            return q
 
p = getPrime(512)
q = obfuscate(p, 5)
e = 65537
n = p*q
print(f'n = {n}')
 
assert 114514 ** x % p == 1
m = m ^ (x**2)
c = pow(m, e, n)
print(f'c = {c}')
 
'''
n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
'''

题目里的fermat暗示与费马定理有关。看p、q的生成过程，可以大概猜出pq是相近的，至于obfuscate里while循环里的内容看不太懂。用yafu工具试着分解一下n，就得到了。再用基础方法解rsa，得到m。

assert 114514 ** x % p == 1

由这一句可以得到x与p的关系：$114514^{x} mod p\equiv 1$，变形得到：$114514^{x} \equiv 1mod p$，判断一下114514和p是否互质，发现是的，那么就可以使用费马小定理了，把a当作114514，则x=p-1。故m = m ^ $(p-1)^{2}$，就能解出flag了。代码如下：

from gmpy2 import *
from Crypto.Util.number import *
 
e = 65537
n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
 
p = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734648016476153593841839977704512156756634066593725142934001
q = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734646483980612727952939084061619889139517526028673988305393
d = invert(e,(p-1)*(q-1))
m = pow(c,d,n)
 
flag = m ^ (p-1)**2
print(long_to_bytes(flag))

题目来源2022祥云杯。

Long_But_Short

题目：

from Crypto.Util.number import *
from secret import flag
flag = bytes_to_long(flag)

p = getPrime(1024)
q = p+1
assert flag**2 < p
a = pow(flag+p, q, p)

print('p=',p) 
print('a=',a)

'''
p= 132485702522161146757217734716447479208806639208543182360084149642567339473293168036770464973129405874692085101982109256055320486303869520189058357502693388509190430447787056423080714947904812339604787610679547711291646116182650401371922642011766279740399192613052280061981102203595808184804858315094410004923
a= 1718205151527213531940354061216609955728503626623437131525315244599535856595391286686273033612529023037466615611832668265075325829196053041494716601943531710744433426780718569225
'''

由题目可以得到如下关系：

• $q = p + 1$
• $flag^{2} < p$
• $a = (flag+p)^{q} \space mod \space p$

把$q = p + 1$代入等式中得到:

$a = (flag+p)^{p+1} \space mod \space p = (flag+p)^{p-1+2} \space mod \space p$

由费马小定理，$a^{p-1} \equiv 1modp$，把$(flag+p)$当作$a$

故$(flag+p)^{p-1} \space mod \space p\equiv 1$

可直接约去，所以原式化简为：

$a \equiv (flag+p)^{2} \space mod \space p$，

$(flag+p)^{2} mod p\equiv(flag^{2}+2flagp+p^2)modp\equiv flag^{2}modp$，

因为上面知道了$flag^{2}<p$，故$flag^{2}modp \equiv flag^{2}$。

综上，对a开方即为最终flag。

代码如下：

print(long_to_bytes(iroot(a,2)[0]))
#SYC{7ca905c9dbba1ffe7ff0ee3ee93f1ac1}

题目来源：Geek Challenge 2022

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com