趣题分享[3] -- RSA 相关题目
[鹤城杯 2021]BabyRSA
题面
# [鹤城杯 2021]BabyRSA
from Crypto.Util.number import getPrime, bytes_to_long
# from secret import flag
flag = b'flag{test}'
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724 # msb 1024 - 724
hint2 = q % (2 ** 265) # lsb 265
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)
# Data
hint1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
hint2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
ct = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
Idea
Reference:
我的推导
Solution
SageMath 10.3
q_low_inv = power_mod(hint2, -1, 2 ** 265)
p_low = n * q_low_inv % (2 ** 265)
print(f'{p_low = }')
p_msb = hint1 << 724
P.<p_mid> = PolynomialRing(Zmod(n))
f = p_msb + p_mid * (2 ** 265) + p_low
# beta: 未知数 / N
ans = f.monic().small_roots(X=2 ** (1024 - (1024 - 724) - 265), beta=0.2, epsilon=0.01)
print(f'{ans = }')
if ans == []:
print('small_roots Failed')
p = int(f(ans[0])) # 必要的强制类型转换, 不然 mod n 传递
q = n // p # 会变为 (n % n) // (p % n) | 0 // p | 0
assert p * q == n, 'p * q != n'
d = inverse_mod(e, (p - 1) * (q - 1))
m = power_mod(ct, d, n)
print(long_to_bytes(m))
NPUCTF2020 -- EzRSA
西北工业大学的比赛
题目、思路、Exploit 均在如下代码中
# NPUCTF2020 EzRSA
from gmpy2 import lcm , powmod , invert , gcd , mpz, isqrt, invert
from Crypto.Util.number import getPrime, long_to_bytes
from sympy import nextprime
from random import randint
p = getPrime(1024)
q = getPrime(1024)
n = p * q
gift = lcm(p - 1 , q - 1)
# https://www.zhihu.com/question/493156617
# https://www.wikiwand.com/en/RSA_(cryptosystem)
e = 54722 # not is prime
flag = b'NPUCTF{******************}'
m = int.from_bytes(flag , 'big')
c = powmod(m , e , n)
print('n = ' , n)
print('gift = ' , gift)
print('c = ' , c)
# Data
n = 17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
gift = 2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104
c = 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
# Idea
# https://oi-wiki.org/math/number-theory/gcd/#%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0
# GCD(a, b) * LCM(a, b) = a * b
# GCD(p - 1, q - 1) * LCM(p - 1, q - 1) = (p - 1) * (q - 1)
# GCD(p - 1, q - 1) * LCM(p - 1, q - 1) = Phi(n) # totient function
# Solution
# https://www.cnblogs.com/vict0r/p/13723450.html
print(f'{bin(n) = }')
print(f'{bin(gift) = }')
print(f'{n.bit_length() - gift.bit_length() = } bits') # 3 bits
# gift * gcd = (p-1) * (q-1)
# gift % gcd = 0
for gcd_val in range(0b100, 0b111): # 3 bits | 0b100 -> 0b111
phi = gift * gcd_val
try:
d = invert(e // 2, phi) # e 不是质数, 无法直接求逆, 但是 e // 2 是质数
# c = m^e % n | c = m^((e//2) * 2) % n | c = (m^2)^(e//2) % n
m_2 = pow(c, int(d), n)
flag = long_to_bytes(isqrt(m_2))
print(flag)
except ZeroDivisionError:
continue
可怜的 RSA
题面
两个文件,在Data部分
Data
public.key
-----BEGIN PUBLIC KEY-----
MIIBJDANBgkqhkiG9w0BAQEFAAOCAREAMIIBDAKCAQMlsYv184kJfRcjeGa7Uc/4
3pIkU3SevEA7CZXJfA44bUbBYcrf93xphg2uR5HCFM+Eh6qqnybpIKl3g0kGA4rv
tcMIJ9/PP8npdpVE+U4Hzf4IcgOaOmJiEWZ4smH7LWudMlOekqFTs2dWKbqzlC59
NeMPfu9avxxQ15fQzIjhvcz9GhLqb373XDcn298ueA80KK6Pek+3qJ8YSjZQMrFT
+EJehFdQ6yt6vALcFc4CB1B6qVCGO7hICngCjdYpeZRNbGM/r6ED5Nsozof1oMbt
Si8mZEJ/Vlx3gathkUVtlxx/+jlScjdM7AFV5fkRidt0LkwosDoPoRz/sDFz0qTM
5q5TAgMBAAE=
-----END PUBLIC KEY-----
flag.enc
GVd1d3viIXFfcHapEYuo5fAvIiUS83adrtMW/MgPwxVBSl46joFCQ1plcnlDGfL19K/3PvChV6n5QGohzfVyz2Z5GdTlaknxvHDUGf5HCukokyPwK/1EYU7NzrhGE7J5jPdi0Aj7xi/Odxy0hGMgpaBLd/nL3N8O6i9pc4Gg3O8soOlciBG/6/xdfN3SzSStMYIN8nfZZMSq3xDDvz4YB7TcTBh4ik4wYhuC77gmT+HWOv5gLTNQ3EkZs5N3EAopy11zHNYU80yv1jtFGcluNPyXYttU5qU33jcp0Wuznac+t+AZHeSQy5vk8DyWorSGMiS+J4KNqSVlDs12EqXEqqJ0uA==
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from base64 import b64decode
path = '/RSA/'
# 读取public key
# with open(path, 'r') as f:
# data = f.read()
# openssl rsa -in public.key -pubin -text -noout
"""
Public-Key: (2070 bit)
Modulus:
25:b1:8b:f5:f3:89:09:7d:17:23:78:66:bb:51:cf:
f8:de:92:24:53:74:9e:bc:40:3b:09:95:c9:7c:0e:
38:6d:46:c1:61:ca:df:f7:7c:69:86:0d:ae:47:91:
c2:14:cf:84:87:aa:aa:9f:26:e9:20:a9:77:83:49:
06:03:8a:ef:b5:c3:08:27:df:cf:3f:c9:e9:76:95:
44:f9:4e:07:cd:fe:08:72:03:9a:3a:62:62:11:66:
78:b2:61:fb:2d:6b:9d:32:53:9e:92:a1:53:b3:67:
56:29:ba:b3:94:2e:7d:35:e3:0f:7e:ef:5a:bf:1c:
50:d7:97:d0:cc:88:e1:bd:cc:fd:1a:12:ea:6f:7e:
f7:5c:37:27:db:df:2e:78:0f:34:28:ae:8f:7a:4f:
b7:a8:9f:18:4a:36:50:32:b1:53:f8:42:5e:84:57:
50:eb:2b:7a:bc:02:dc:15:ce:02:07:50:7a:a9:50:
86:3b:b8:48:0a:78:02:8d:d6:29:79:94:4d:6c:63:
3f:af:a1:03:e4:db:28:ce:87:f5:a0:c6:ed:4a:2f:
26:64:42:7f:56:5c:77:81:ab:61:91:45:6d:97:1c:
7f:fa:39:52:72:37:4c:ec:01:55:e5:f9:11:89:db:
74:2e:4c:28:b0:3a:0f:a1:1c:ff:b0:31:73:d2:a4:
cc:e6:ae:53
Exponent: 65537 (0x10001)
"""
n = 0x25b18bf5f389097d17237866bb51cff8de922453749ebc403b0995c97c0e386d46c161cadff77c69860dae4791c214cf8487aaaa9f26e920a977834906038aefb5c30827dfcf3fc9e9769544f94e07cdfe0872039a3a6262116678b261fb2d6b9d32539e92a153b3675629bab3942e7d35e30f7eef5abf1c50d797d0cc88e1bdccfd1a12ea6f7ef75c3727dbdf2e780f3428ae8f7a4fb7a89f184a365032b153f8425e845750eb2b7abc02dc15ce0207507aa950863bb8480a78028dd62979944d6c633fafa103e4db28ce87f5a0c6ed4a2f2664427f565c7781ab6191456d971c7ffa395272374cec0155e5f91189db742e4c28b03a0fa11cffb03173d2a4cce6ae53
e = 0x10001
# read c
with open(path + 'flag.enc', 'r') as f:
base_c = f.read()
c = b64decode(base_c)
p = 3133337
q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
key_info = RSA.construct((n, e, d, p, q))
# key = RSA.importKey(key_info.exportKey())
key = PKCS1_OAEP.new(key_info)
flag = key.decrypt(c) # bytes 直接解密
print(flag)
VNCTF 2020 easy_RSA
题面
from random import randint
from gmpy2 import *
from Crypto.Util.number import *
def getprime(bits):
while 1:
n = 1
while n.bit_length() < bits:
n *= next_prime(randint(1, 1000))
if isPrime(n - 1):
return n - 1 # p + 1
m = bytes_to_long(b'flag{************************************}')
p = getprime(505)
q = getPrime(512)
r = getPrime(512)
assert m < q
n = p * q * r
e = 0x10001
d = invert(q ** 2, p ** 2) # q ** 2 * d = 1 mod p ** 2
c = pow(m, 2, r) # quadratic residue
cipher = pow(c, e, n)
print(n)
print(d)
print(cipher)
Solution
SageMath Code
from sage.all import * # 不置顶导入会导致部分变量/函数被导入污染
import itertools
import primefac # pip install primefac
from random import randint
from gmpy2 import *
from Crypto.Util.number import *
n = 7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409
d = 7515987842794170949444517202158067021118454558360145030399453487603693522695746732547224100845570119375977629070702308991221388721952258969752305904378724402002545947182529859604584400048983091861594720299791743887521228492714135449584003054386457751933095902983841246048952155097668245322664318518861440
c = 1618155233923718966393124032999431934705026408748451436388483012584983753140040289666712916510617403356206112730613485227084128314043665913357106301736817062412927135716281544348612150328867226515184078966397180771624148797528036548243343316501503364783092550480439749404301122277056732857399413805293899249313045684662146333448668209567898831091274930053147799756622844119463942087160062353526056879436998061803187343431081504474584816590199768034450005448200
e = 0x10001
# p, q, r 加上1均有一大堆小因子,故采用 William's p+1 算法来分解掉 n
p = primefac.williams_pp1(n)
q_2 = invert(d, p ** 2)
# q > p, 所以在题目 d = invert(q ** 2, p ** 2) 中会损失信息, 但位差很小, 于是爆破 k
for k in itertools.count(0): # 从 0 开始枚举 k
res = iroot(q_2 + k * (p ** 2), 2)
if res[1]:
q = res[0]
break
print(f'{q = }')
r = n // (p * q)
print(f'{r = }')
assert r * p * q == n, 'r * p * q != n'
real_d = invert(e, (p - 1) * (q - 1) * (r - 1))
quadratic_residue_c = powmod(c, real_d, n)
# 也可以使用别的方法求解二次剩余
ans = Mod(ZZ(quadratic_residue_c), r).nth_root(2, all=True)
for i in ans:
m = long_to_bytes(int(i))
if all(32 <= c < 128 for c in m):
print(m)
break
# b'flag{fd462593-25e4-4631-a96a-0cd5c72b2d1b}'
DASCTF X GFCTF 2022 十月挑战赛 RSA
题面
from Crypto.Util.number import bytes_to_long, getPrime
from secret import flag # type: ignore
def encrypt1(n):
n1 = hex(n >> 200).encode() # 右移200位后转为16进制, msb
n2 = str(hex(n))[20:].encode() # 转hex, 再转为bytes, lsb, index 20开始
return n1, n2
def encrypt2(m, n_1):
c_1 = pow(m, e_1, n_1) # pow(m, 65537, n_1)
print('c_1 = '+str(c_1))
def encrypt3(m, n_2):
c_2 = pow(m, e_2, n_2) # pow(m, 3, n_2)
print('c_2 = '+str(c_2))
def encrypt4(m):
k = getPrime(512)
m = m % k # (0, k-1) # m < k, mod 无效
# ^未知^已知
c_3 = pow(m, e_2, n_3) # pow(m, 3, n_3)
#^已知 ^已知 ^已知
print('c_3 = ' + str(c_3))
print('m = ' + str(m))
print('k = ' + str(k))
m1, m2 = encrypt1(flag)
print('m1 = ' + str(m1))
print('m2 = ' + str(m2))
m1 = bytes_to_long(m1)
m2 = bytes_to_long(m2)
print('n_2 = ' + str(n_2))
print('n_3 = ' + str(n_3))
print('e_1 = ' + str(e_1))
print('e_2 = ' + str(e_2))
encrypt2(m1, n_1)
encrypt3(n_1, n_2)
encrypt4(m2)
Data
n_2 = 675835056744450121024004008337170937331109883435712066354955474563267257037603081555653829598886559337325172694278764741403348512872239277008719548968016702852609803016353158454788807563316656327979897318887566108985783153878668451688372252234938716250621575338314779485058267785731636967957494369458211599823364746908763588582489400785865427060804408606617016267936273888743392372620816053927031794575978032607311497491069242347165424963308662091557862342478844612402720375931726316909635118113432836702120449010
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
e_1 = 65537
e_2 = 3
c_1 = 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533
c_2 = 332431
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431
Solution
SageMath Code
from sage.all import factor
from gmpy2 import invert, iroot, powmod
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime, isPrime
import itertools
n_2 = 675835056744450121024004008337170937331109883435712066354955474563267257037603081555653829598886559337325172694278764741403348512872239277008719548968016702852609803016353158454788807563316656327979897318887566108985783153878668451688372252234938716250621575338314779485058267785731636967957494369458211599823364746908763588582489400785865427060804408606617016267936273888743392372620816053927031794575978032607311497491069242347165424963308662091557862342478844612402720375931726316909635118113432836702120449010
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
e_1 = 65537
e_2 = 3
c_1 = 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533
c_2 = 332431
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431
enc_4_m = m
# reverse encrypt3
n_1 = None
for kk in itertools.count(0):
base = n_2 * kk + c_2
maybe_n_1 = iroot(base, 3)
if maybe_n_1[1]:
print(f'found n_1: {maybe_n_1}')
n_1 = int(maybe_n_1[0])
break
# reverse encrypt2
print(f'{isPrime(n_1) = }')
print(f'{factor(n_1) = }') # 使用 sage 中 factor 函数拿到分解
n_1_p = 2224243981
n_1_q = 2732337821
n_1_r = 11585031296201346891716939633970482508158508580350404805965250133832632323150440185890235814142601827544669601048550999405490149435265122374459158586377571
n_1_phi = (n_1_p - 1) * (n_1_q - 1) * (n_1_r - 1)
n_1_d = invert(e_1, n_1_phi)
print(f'{n_1_d = }')
m1 = int(powmod(c_1, n_1_d, n_1))
try:
print(f'{m1 = }')
print(f'{bin(m1) = }')
m1_bytes = long_to_bytes(m1)
print(f'{m1_bytes = }') # m1 = b'0x666c61677b3230366538353964'
print(f'{len(m1_bytes) = }') # 28 bytes | 28 * 8 = 224 bits + 200 bits = 424 bits
except Exception as error:
print(f'{error = }')
# reverse encrypt4
print(f'{bin(enc_4_m) = }')
print(f'{enc_4_m.bit_length() / 8 = }') # 无法整除
# reverse encrypt1 | merge m1 and m2 | 手动选交集, 删除 m2 在 m1 中重复的部分 | 手动确实不优雅, 但写代码的时候脑子卡住了, 没有想到更好的办法
m = 0b1100000111100000110110001101100011011001100011001101100011000100110110001101110011011101100010001100110011001000110011001100000011001100110110001101100011010100110011001110000011001100110101001100110011100100110110001101000011001100111000001101100011010100110011001110000011001100110101001100110011010000110110001100110011001100110100001101100011011000110011001101100011001100110000001100110011000000110110001100110011011000110010001100110011000100110011001100100011001100110111001100110011010100110011001101110011011000110010001101100011001000110110001101100011001100111001001101100011011000110011001101010011011101100100
temp = long_to_bytes(m)
print(f'{temp = }')
print(long_to_bytes(int(temp, 16)))
# b'flag{206e859d8e854c4f600cb12757bbf9f5}'