潜心的博客

复现东华杯2021的一道Crypto题-fermat's revenge

2022-5-8 CryptoRSA费马小定理东华杯2021

# fermat's revenge

有两个附件

  • task.py
from Crypto.Util.number import *
f = open('flag.txt', 'rb')
m = bytes_to_long(f.read())
f.close()
e = 65537
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m, e, n)
hint = pow(1010 * p + 1011, q, n)
f = open('cipher.txt', 'w')
f.write(f'n={n}\n')
f.write(f'c={c}\n')
f.write(f'hint={hint}\n')
f.close()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • cipher.txt
n=17329555687339057933030881774167606066714011664369940819755094697939414110116183129515036417930928381309923593306884879686961969722610261114896200690291299753284120079351636102685226435454462581742248968732979816910255384339882675593423385529925794918175056364069416358095759362865710837992174966213332948216626442765218056059227797575954980861175262821459941222980957749720949816909119263643425681517545937122980872133309062049836920463547302193585676588711888598357927574729648088370609421283416559346827315399049239357814820660913395553316721927867556418628117971385375472454118148999848258824753064992040468588511
c=2834445728359401954509180010018035151637121735110411504246937217024301211768483790406570069340718976013805438660602396212488675995602673107853878297024467687865600759709655334014269938893756460638324659859693599161639448736859952750381592192404889795107146077421499823006298655812398359841137631684363428490100792619658995661630533920917942659455792050032138051272224911869438429703875012535681896010735974555495618216882831524578648074539796556404193333636537331833807459066576022732553707927018332334884641370339471969967359580724737784159811992637384360752274204462169330081579501038904830207691558009918736480389
hint=2528640120640884291705022551567142949735065756834488816429783990402901687493207894594113717734719036126087363828359113769238235697788243950392064194097056579105620723640796253143555383311882778423540515270957452851097267592400001145658904042191937942341842865936546187498072576943297002184798413336701918670376291021190387536660070933700475110660304652647893127663882847145502396993549034428649569475467365756381857116208029508389607872560487325166953770793357700419069480517845456083758105937644350450559733949764193599564499133714282286339445501435278957250603141596679797055178139335763901195697988437542180256184
1
2
3

# 费马小定理

如果p是一个质数，而整数a不是p的倍数，则有

应用：

求

所以

费马小定理_百度百科 (baidu.com) (opens new window)

费马小定理（Fermat's Little Theorem） - 知乎 (zhihu.com) (opens new window)

# 我的思路

虽然推导不出，但在此记录下

hint = pow(1010 * p + 1011, q, n)
1

然后就发现无法继续推导下去了，也无法直接爆破。

# 复现

参考：[东华杯] 第七届东华杯上海市大学生网络安全大赛 Crypto方向 团队writeup - 知乎 (zhihu.com) (opens new window)

对于之前的推导过程，两边同时模 ，并不能推出来，这里等式两边同时模 试试

由费马小定理可以知道， ，所以这里需要从 凑出 ，而

即 是 的倍数，而 ，即 也是 的倍数，所以求 和 的最大公约数即可求出

但对于 来说，其中的 非常大，如果直接求最大公约数，可能求不出(时间太久)

p = gcd(pow(1011,n)-h, n)
1

对于 ，两边同时模 ，可得

所以只需要求出 和 的最大公约数即可求出

# exp

import gmpy2
import libnum

n = 17329555687339057933030881774167606066714011664369940819755094697939414110116183129515036417930928381309923593306884879686961969722610261114896200690291299753284120079351636102685226435454462581742248968732979816910255384339882675593423385529925794918175056364069416358095759362865710837992174966213332948216626442765218056059227797575954980861175262821459941222980957749720949816909119263643425681517545937122980872133309062049836920463547302193585676588711888598357927574729648088370609421283416559346827315399049239357814820660913395553316721927867556418628117971385375472454118148999848258824753064992040468588511
c = 2834445728359401954509180010018035151637121735110411504246937217024301211768483790406570069340718976013805438660602396212488675995602673107853878297024467687865600759709655334014269938893756460638324659859693599161639448736859952750381592192404889795107146077421499823006298655812398359841137631684363428490100792619658995661630533920917942659455792050032138051272224911869438429703875012535681896010735974555495618216882831524578648074539796556404193333636537331833807459066576022732553707927018332334884641370339471969967359580724737784159811992637384360752274204462169330081579501038904830207691558009918736480389
h = 2528640120640884291705022551567142949735065756834488816429783990402901687493207894594113717734719036126087363828359113769238235697788243950392064194097056579105620723640796253143555383311882778423540515270957452851097267592400001145658904042191937942341842865936546187498072576943297002184798413336701918670376291021190387536660070933700475110660304652647893127663882847145502396993549034428649569475467365756381857116208029508389607872560487325166953770793357700419069480517845456083758105937644350450559733949764193599564499133714282286339445501435278957250603141596679797055178139335763901195697988437542180256184
e = 65537

p = gmpy2.gcd(pow(1011,n,n)-h, n)
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(libnum.n2s(int(m)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
b'flag{1d2f28834ecbd1983b62d30f4723476e}'
1

复现蓝帽杯2022一道Crypto题-corrupted_key