640 words
3 minutes
VCTF-Crypto-wp

战队里有人找我问这个比赛的题,因为题量挺少的,就顺便抽空记记(

1,RRSA#

题目:

RRSA.py (点击展开)```python from flag import flag import random from Crypto.Util.number import * def genprime(): o = getPrime(300) while True: r = random.randint(2**211,2**212) if isPrime(o*r+1): return o, o*r+1 ```python from flag import flag import random from Crypto.Util.number import * def genprime(): o = getPrime(300) while True: r = random.randint(2**211,2**212) if isPrime(o*r+1): return o, o*r+1 o1, p = genprime() o2, q = genprime() n=p*q g = random.randint(2,n) order = o1*o2

a = pow(g, (p-1)*(q-1)//order, n) assert pow(a,order,n)==1

m = bytes_to_long(flag) e = 65537 c = pow(m,e,n) print(f’n={n}’) print(f’c={c}’) print(f’a={a}’) print(f’o={order}’) n=44435425447782114838897637647733409614831121089064725526413247701631122523646623518523253532066782191116739274354991533158902831935676078270115998050827358178237970133151467497051097694866238654012042884894924846645692294679774577780414805605811029994570132760841672754334836945991390844881416693502552870759 c=41355409695119524180275572228024314281790321005050664347253778436753663918879919757571129194249071204946415158483084730406579433518426895158142068246063333111438863836668823874266012696265984976829088976346775293102571794377818611709336242495598331872036489022428750111592728015245733975923531682859930386731 a=39844923600973712577104437232871220768052114284995840460375902596405104689968610170336151307934820030811039502338683925817667771016288030594299464019664781911131177394369348831163266849069740191783143327911986419528382896919157135487360024877230254274474109707112110411601273850406237677432935818199348150470 o=1745108106200960949680880500144134006212310627077303652648249235148621661187609612344828833696608872318217367008018829485062303972702933973340909520462917612611270028511222134076453


</details>


**解答:**

因为我们知道:

$$
phi=o*r1*r2=(p-1)(q-1)=n-p-q+1=n+1-(p+q)
$$
所以我们有:$p+q=n+1-o*r1*r2$

并且我们知道了o和n的值,所以我们可以构造出这样的格:

$$
\begin{pmatrix}2^{144}&-o\newline 0 &n+1\end{pmatrix}
$$
使得下式成立:

$$
\begin{pmatrix}r1*r2,\ 1\end{pmatrix}*\begin{pmatrix}2^{144}&-o\newline 0 &n+1 \end{pmatrix}=\begin{pmatrix}2^{144}*r1*r2,\ p+q\end{pmatrix}
$$
代码如下:

<details>
    <summary>exp (点击展开)</summary>
```python
from Crypto.Util.number import *
from gmpy2 import *
n=44435425447782114838897637647733409614831121089064725526413247701631122523646623518523253532066782191116739274354991533158902831935676078270115998050827358178237970133151467497051097694866238654012042884894924846645692294679774577780414805605811029994570132760841672754334836945991390844881416693502552870759
c=41355409695119524180275572228024314281790321005050664347253778436753663918879919757571129194249071204946415158483084730406579433518426895158142068246063333111438863836668823874266012696265984976829088976346775293102571794377818611709336242495598331872036489022428750111592728015245733975923531682859930386731
a=39844923600973712577104437232871220768052114284995840460375902596405104689968610170336151307934820030811039502338683925817667771016288030594299464019664781911131177394369348831163266849069740191783143327911986419528382896919157135487360024877230254274474109707112110411601273850406237677432935818199348150470
o=1745108106200960949680880500144134006212310627077303652648249235148621661187609612344828833696608872318217367008018829485062303972702933973340909520462917612611270028511222134076453
s = 2**144
P = [[s, -o], [0, (n+1)]]
P = matrix(ZZ, P)
res = abs(P.LLL()[0][0])//s
#print(res)
pq = n+1-res*o
qp = iroot(pq**2-4*n, 2)[0]
p = (pq+qp)//2
q = n // p
#assert (p-1)*(q-1)==o*res
e = 65537
d = invert(e, o*res)
print(long_to_bytes(int(pow(c,d,n))))

当然,比起上面的那种,我更推荐下面这种:

(1o/s0(n+1)/s)\begin{pmatrix}1&-o/s\newline 0 &(n+1)/s \end{pmatrix} (r1r2, 1)(1o/s0(n+1)/s)=(r1r2, (p+q)/s)\begin{pmatrix}r1*r2,\ 1\end{pmatrix}*\begin{pmatrix}1&-o/s\newline 0 &(n+1)/s \end{pmatrix}=\begin{pmatrix}r1*r2,\ (p+q)/s\end{pmatrix}
exp1 (点击展开)```python from Crypto.Util.number import * from gmpy2 import * n=44435425447782114838897637647733409614831121089064725526413247701631122523646623518523253532066782191116739274354991533158902831935676078270115998050827358178237970133151467497051097694866238654012042884894924846645692294679774577780414805605811029994570132760841672754334836945991390844881416693502552870759 c=41355409695119524180275572228024314281790321005050664347253778436753663918879919757571129194249071204946415158483084730406579433518426895158142068246063333111438863836668823874266012696265984976829088976346775293102571794377818611709336242495598331872036489022428750111592728015245733975923531682859930386731 a=39844923600973712577104437232871220768052114284995840460375902596405104689968610170336151307934820030811039502338683925817667771016288030594299464019664781911131177394369348831163266849069740191783143327911986419528382896919157135487360024877230254274474109707112110411601273850406237677432935818199348150470 o=1745108106200960949680880500144134006212310627077303652648249235148621661187609612344828833696608872318217367008018829485062303972702933973340909520462917612611270028511222134076453 s = 2**144 P = [[1, -o//s], [0, (n+1)//s]] P = matrix(ZZ, P) res = abs(P.LLL()[0][0]) #print(res) pq = n+1-res*o qp = iroot(pq**2-4*n, 2)[0] p = (pq+qp)//2 q = n // p #assert (p-1)*(q-1)==o*res e = 65537 d = invert(e, o*res) print(long_to_bytes(int(pow(c,d,n))))

</details>

<hr style="border: 0.5px solid black;"/>

## 2,狂飙

**题目:**

<details>
    <summary>kuangbiao.sage (点击展开)</summary>
```python
import os
from secrets import flag
from Crypto.Util.number import *
from Crypto.Cipher import AES
m = 88007513702424243702066490849596817304827839547007641526433597788800212065249
key = os.urandom(24)
key = bytes_to_long(key)
n = m % key
flag += (16 - len(flag) % 16) * b'\x00'
iv = os.urandom(16)
aes = AES.new(key,AES.MODE_CBC,iv)
enc_flag = aes.encrypt(flag)
```python
import os
from secrets import flag
from Crypto.Util.number import *
from Crypto.Cipher import AES
m = 88007513702424243702066490849596817304827839547007641526433597788800212065249
key = os.urandom(24)
key = bytes_to_long(key)
n = m % key
flag += (16 - len(flag) % 16) * b'\x00'
iv = os.urandom(16)
aes = AES.new(key,AES.MODE_CBC,iv)
enc_flag = aes.encrypt(flag)print(n)
print(enc_flag)
print(iv)
#103560843006078708944833658339172896192389513625588
#b'\xfc\x87\xcb\x8e\x9d\x1a\x17\x86\xd9~\x16)\xbfU\x98D\xfe\x8f\xde\x9c\xb0\xd1\x9e\xe7\xa7\xefiY\x95C\x14\x13C@j1\x9d\x08\xd9\xe7W>F2\x96cm\xeb'
#b'UN\x1d\xe2r<\x1db\x00\xdb\x9a\x84\x1e\x82\xf0\x86'

解答:

题目实现了一个正常的AES-CBC加密,并给了我们密文cm mod key的结果n初始向量iv

很明显——我们要进行AES-CBC解密的话,key也得知道。

n=m mod keyn=m\ mod\ keym>keym>key(这一点可以通过分析m与n得到),即mn=a1keym-n=a_1*key

也就是说:mnm-n这个数里包含了key这个值,但得注意一件事——key并不是素数,所以我们得用divisors()。

exp (点击展开)```python # sage n = 103560843006078708944833658339172896192389513625588 c = b'\xfc\x87\xcb\x8e\x9d\x1a\x17\x86\xd9~\x16)\xbfU\x98D\xfe\x8f\xde\x9c\xb0\xd1\x9e\xe7\xa7\xefiY\x95C\x14\x13C@j1\x9d\x08\xd9\xe7W>F2\x96cm\xeb' iv = b'UN\x1d\xe2r<\x1db\x00\xdb\x9a\x84\x1e\x82\xf0\x86' ```python # sage n = 103560843006078708944833658339172896192389513625588 c = b'\xfc\x87\xcb\x8e\x9d\x1a\x17\x86\xd9~\x16)\xbfU\x98D\xfe\x8f\xde\x9c\xb0\xd1\x9e\xe7\xa7\xefiY\x95C\x14\x13C@j1\x9d\x08\xd9\xe7W>F2\x96cm\xeb' iv = b'UN\x1d\xe2r<\x1db\x00\xdb\x9a\x84\x1e\x82\xf0\x86' m = 88007513702424243702066490849596817304827839547007641526433597788800212065249 key = m-n from Crypto.Util.number import * from Crypto.Cipher import AES for k in key.divisors(): k = long_to_bytes(k,24) aes = AES.new(k,AES.MODE_CBC,iv) flag = aes.decrypt(c) if b'flag{' in flag: print(flag) break ```
VCTF-Crypto-wp
https://shinichicun.top/posts/vctf-crypto-wp/
Author
Shin
Published at
2024-03-19