LOV3

无限进步

首页 已发布 标签 友链 关于

趣题分享[3] -- RSA 相关题目

2024-06-02 12 min read # math # crypto

[鹤城杯 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:

鹤城杯2021 Crypto Writes up

我的推导

q≡qlow(mod2265)q=qlow+2265∗kn=p∗qn=p∗(qlow+2265∗k)n=p∗qlow+p∗2265∗kn=p∗qlow+2265∗k∗pn∗qlow−1=p∗qlow∗qlow−1+p∗2265∗k∗qlow−1n∗qlow−1=p+p∗2265∗k∗qlow−1n∗qlow−1=p+2265∗(p∗k∗qlow−1)n∗qlow−1≡p(mod2265)plow≡n∗qlow−1(mod2265)\begin{aligned} q \equiv q_{low} \pmod{2^{265}} \\ q = q_{low} + 2^{265} * k \\ n = p * q \\ n = p * (q_{low} + 2^{265} * k) \\ n = p * q_{low} + p * 2^{265} * k \\ n = p * q_{low} + 2^{265} * k * p \\ n * {q_{low}}^{-1} = p * q_{low} * {q_{low}}^{-1} + p * 2^{265} * k * {q_{low}}^{-1} \\ n * {q_{low}}^{-1} = p + p * 2^{265} * k * {q_{low}}^{-1} \\ n * {q_{low}}^{-1} = p + 2^{265} * (p * k * {q_{low}}^{-1}) \\ n * {q_{low}}^{-1} \equiv p \pmod{2^{265}} \\ p_{low} \equiv n * {q_{low}}^{-1} \pmod{2^{265}} \\ \end{aligned}

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}'
RSS   DK盾 - 高防服务器赞助商