RSA_practice

记录RSA入门的一些做题笔记

DiceCTF 2022 baby-rsa

1
2
3
4
5
6
7
8
9
10
11
def getAnnoyingPrime(nbits, e):
	while True:
		p = getPrime(nbits)
		if (p-1) % e**2 == 0:
			return p

nbits = 128
e = 17

p = getAnnoyingPrime(nbits, e)
q = getAnnoyingPrime(nbits, e)

p,q为128为的素数，在yafu中很快可以分解出来。这题难点在于(p-1) % e^2 == 0和 (q-1) % e^2 == 0,所以d = gmpy2.invert(e, (p-1)*(q-1))会报错。实在不会只能在网上找东西来学习了。

当e较小时可以通过sage 用 GF(p)(c).nth_root(e, all=True)处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *

p = 172036442175296373253148927105725488217
q = 337117592532677714973555912658569668821
e = 17
c = 19441066986971115501070184268860318480501957407683654861466353590162062492971

for mp in GF(p)(c).nth_root(e, all=True):
    for mq in GF(q)(c).nth_root(e, all=True):
        m = crt([ZZ(mp), ZZ(mq)], [p, q])
        flag = long_to_bytes(m)
        if flag.startswith(b"dice{"):
            print(flag)

# dice{cado-and-sage-say-hello}

这部分代码执行了解密过程。

  1. GF(p)(c).nth_root(e, all=True)：这行代码计算了 GF(p) 上的 c 的 e 次方根，并使用all=True选项获取了所有可能的解。GF(p) 是定义在有限域上的多项式环，这里将其用于计算模 p 下的多项式。
  2. GF(q)(c).nth_root(e, all=True)：这行代码计算了 GF(q) 上的 c 的 e 次方根，并使用all=True选项获取了所有可能的解。GF(q) 是定义在有限域上的多项式环，这里将其用于计算模 q 下的多项式。
  3. crt([ZZ(mp), ZZ(mq)], [p, q])：这行代码使用了中国剩余定理（Chinese Remainder Theorem, CRT）。crt函数接受两个列表作为参数，第一个列表包含两个部分解密值 mp 和 mq，第二个列表包含对应的模数 p 和 q。它将这些值合并为一个明文值 m。
  4. flag = long_to_bytes(m)：这行代码将解密后的明文 m 转换为字节形式。long_to_bytes函数将长整型数值转换为字节字符串。
  5. if flag.startswith(b"dice{"):：这行代码检查解密出的明文是否以 b"dice{" 开头，判断是否解密出了正确的结果。
  6. print(flag)：如果解密出的明文满足条件，则打印出明文结果

Maple CTF 2022 brsaby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

msg = bytes_to_long(FLAG)
p = getPrime(512)
q = getPrime(512)
N = p*q
e = 0x10001
enc = pow(msg, e, N)
hint = p**4 - q**3

print(f"{N = }")
print(f"{e = }")
print(f"{enc = }")
print(f"{hint = }")

'''
N = 134049493752540418773065530143076126635445393203564220282068096099004424462500237164471467694656029850418188898633676218589793310992660499303428013844428562884017060683631593831476483842609871002334562252352992475614866865974358629573630911411844296034168928705543095499675521713617474013653359243644060206273
e = 65537
enc = 110102068225857249266317472106969433365215711224747391469423595211113736904624336819727052620230568210114877696850912188601083627767033947343144894754967713943008865252845680364312307500261885582194931443807130970738278351511194280306132200450370953028936210150584164591049215506801271155664701637982648648103
hint = 20172108941900018394284473561352944005622395962339433571299361593905788672168045532232800087202397752219344139121724243795336720758440190310585711170413893436453612554118877290447992615675653923905848685604450760355869000618609981902108252359560311702189784994512308860998406787788757988995958832480986292341328962694760728098818022660328680140765730787944534645101122046301434298592063643437213380371824613660631584008711686240103416385845390125711005079231226631612790119628517438076962856020578250598417110996970171029663545716229258911304933901864735285384197017662727621049720992964441567484821110407612560423282
'''

由题目可知hint=p^4-q^3,p,q都是512位的素数，所以p，q很接近所以hint约等于（p-1）*p^3约等于p^4

所以在sage中跑出p，q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from sage.all import *

N = 134049493752540418773065530143076126635445393203564220282068096099004424462500237164471467694656029850418188898633676218589793310992660499303428013844428562884017060683631593831476483842609871002334562252352992475614866865974358629573630911411844296034168928705543095499675521713617474013653359243644060206273
e = 65537
enc = 110102068225857249266317472106969433365215711224747391469423595211113736904624336819727052620230568210114877696850912188601083627767033947343144894754967713943008865252845680364312307500261885582194931443807130970738278351511194280306132200450370953028936210150584164591049215506801271155664701637982648648103
hint = 20172108941900018394284473561352944005622395962339433571299361593905788672168045532232800087202397752219344139121724243795336720758440190310585711170413893436453612554118877290447992615675653923905848685604450760355869000618609981902108252359560311702189784994512308860998406787788757988995958832480986292341328962694760728098818022660328680140765730787944534645101122046301434298592063643437213380371824613660631584008711686240103416385845390125711005079231226631612790119628517438076962856020578250598417110996970171029663545716229258911304933901864735285384197017662727621049720992964441567484821110407612560423282

p=int(hint**(1/4))

p1=next_prime(p)
print("p=",p1)
q=N/p1
print("q=",q)


# p=11917573148183173444338385104784582231114229409447057112131253050235068806316496452352116287542988361044359262597423159386263430710183647113674868056755407
# q=11248052945492193606877386307812298309646455365482356576580845624056836046347518805927852646289457003475918197991787867864250859819603651806169306473552239

这里本以为不会刚刚好得到p，q但是经过检验发现这里的确就是p，q的值。

因为对sage不够熟悉，所以还是在python中拿到flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import long_to_bytes, isPrime
import gmpy2

n = 134049493752540418773065530143076126635445393203564220282068096099004424462500237164471467694656029850418188898633676218589793310992660499303428013844428562884017060683631593831476483842609871002334562252352992475614866865974358629573630911411844296034168928705543095499675521713617474013653359243644060206273
e = 65537
c = 110102068225857249266317472106969433365215711224747391469423595211113736904624336819727052620230568210114877696850912188601083627767033947343144894754967713943008865252845680364312307500261885582194931443807130970738278351511194280306132200450370953028936210150584164591049215506801271155664701637982648648103
p= 11917573148183173444338385104784582231114229409447057112131253050235068806316496452352116287542988361044359262597423159386263430710183647113674868056755407
q= 11248052945492193606877386307812298309646455365482356576580845624056836046347518805927852646289457003475918197991787867864250859819603651806169306473552239

d = gmpy2.invert(e, (p-1)*(q-1))

m = pow(c, d, n)

print(long_to_bytes(m))

#b'maple{s0lving_th3m_p3rf3ct_r000ts_1s_fun}'

TSGCTF 2021 Beginner’s Crypto 2021

题目源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from secret import e
from Crypto.Util.number import getStrongPrime, isPrime

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
phi = (p - 1) * (q - 1)

with open('flag.txt', 'rb') as f:
    flag = int.from_bytes(f.read(), 'big')

assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))

e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)

c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)

print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from math import gcd

def extgcd(a, b)://自定义扩展欧几里得算法，得到的x，y为a，b的最大公因数和贝祖等式的解，即a*x0+b*y0=(a,b)
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        (q, a), b = divmod(b, a), a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0

p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837

e = 3 # 这个3确实好猜，以为很简单的，没想到正常inverse没用 :( so sad

N = p * q

e1 = e ** 0x10001
e2 = (e + 2) ** 0x10001

_, x, y = extgcd(e1, e2)
m = pow(c1, x, N) * pow(c2, y, N) % N
//采用模重复平方算法

print(m.to_bytes((m.bit_length() + 7) // 8, 'big'))

在RSA加密算法中，密文 c 是通过对明文 m 进行指数幂运算并取模 N 得到的。即，c ≡ m^e (mod N)。

解密过程就是要找到明文 m，使得 m^e ≡ c (mod N) 成立。

根据扩展欧几里得算法的性质，如果 (x, y) 是 e 和 (p-1)*(q-1) 的贝祖等式的解，那么 (m^e)^x ≡ m^(e*x) ≡ m^(k*(p-1)*(q-1)+1) ≡ m (mod N)，其中 k 是一个整数。

因此，我们可以使用 (m^e)^x ≡ c^x (mod N) 的方式，通过计算 c^x (mod N) 来还原明文 m。

具体到代码中的步骤，通过计算 pow(c1, x, N) 和 pow(c2, y, N)，我们分别得到了 c1^x (mod N) 和 c2^y (mod N)。然后，通过乘法操作 pow(c1, x, N) * pow(c2, y, N) % N，我们得到了 m^e ≡ c1^x * c2^y ≡ (m^x)^e * (m^y)^e ≡ m (mod N)。

因此，通过对密文 c1 和 c2 进行模 N 的幂运算，并通过乘法和模运算得到明文的整数表示 m，就实现了RSA解密过程。

m.to_bytes((m.bit_length() + 7) // 8, 'big') 是将整数 m 转换为字节串形式的表达式。

让我们逐步解释这段代码：

  1. m.bit_length() 返回整数 m 的位数，即表示 m 所需的二进制位数。
  2. + 7 是为了确保在整数位数不是8的倍数的情况下，对字节长度进行向上取整。
  3. // 8 将位数转换为字节数，因为1个字节等于8个位。
  4. 'big' 是一个参数，指示生成的字节串的字节顺序。在这里，'big' 表示使用大端字节顺序，即高位字节排在前面。

因此，m.to_bytes((m.bit_length() + 7) // 8, 'big') 将整数 m 转换为一个字节串，以便以字节形式表示明文。这样可以将明文从整数形式转换为可读的字节串形式，方便查看和处理。

题解都是问gpt的，原理啥的也都一知半解的，这个就当个备份，以后看见相似的题目往上套一下试试。

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br>并没有什么太大的价值给你们<br>谢谢大家