# Rsa module attack

EN | ZH

## Violence breakdown N¶

### Attack conditions¶

When the number of bits in N is less than 512, p and q can be obtained using a strategy of large integer decomposition.

### JarvisOJ - Medium RSA¶

Here we take JarvisOJ - Medium RSA as an example, the topic is as follows

> Remember the veryeasy RSA? Is it not difficult? Then continue to look at this question, this question is not difficult. > Known piece of RSA encrypted information is: 0xdc2eeeb2782c and the public key used for encryption is known: > N = 322831561921859 and = 23 > Please decrypt the plaintext, please convert the number into ascii code submission when submitting > For example, if the plaintext you solved is 0x6162, please submit the string ab > Submit format: PCTF{clear text string}

It can be seen that our N is relatively small, here we directly use factordb to decompose, you can get

$$322831561921859 = 13574881 \times 23781539$$

Then we simply write the program as follows

import gmpy2

p = 13574881

q = 23781539

n = p * q

e = 23
c = 0xdc2eeeb2782c

Phin = (p - 1) * (q - 1)
d = gmpy2.invert (e, phin)
p = gmpy2.powmod(c, d, n)

tmp = hex(p)

print tmp, tmp[2:].decode('hex')


Results are as follows

➜  Jarvis OJ-Basic-easyRSA git:(master) ✗ python exp.py

0x3613559 3a5Y


## p & q Improper decomposition N¶

### Attack conditions¶

We can also attack when p and q are not selected properly in RSA.

### |pq| Very large¶

When pq is large, there must be a certain parameter is small, here we assume p, then we can try to divide the modulus by exhaustive method, and then decompose the modulus, get the confidential parameters and plaintext information. Basically, it is not very feasible.

### |pq| Smaller¶

First of all

$$\frac{(p+q)2}{4}-n=\frac{(p+q)2}{4}-pq=\frac{(p-q)^2}{4}$$

Since |pq| is small, $\frac{(pq)^2}{4}$ is naturally small, and $\frac{(p+q)^2}{4}$ is only slightly larger than N. , so $\frac{p+q}{2}$ is similar to $\sqrt{n}$. Then we can decompose as follows

• Check each integer x of $\sqrt{n}$ in sequence until you find an x such that $x^2-n$ is the square number, denoted as $y^2$
• Then $x^2-n=y^2$, and then decompose N according to the squared difference formula

### p - 1 Smooth¶

When p is a factor of N and p - 1 is smooth, it is possible to use the Pollard's p − 1 algorithm to decompose N, but it is not entirely successful.

Warning

Principle analysis to be completed

### p + 1 Smooth¶

When p is a factor of n and p + 1 is smooth, it may be possible to use the Williams's p + 1 algorithm to decompose N, but it is not entirely successful.

### 2017 SECCON very smooth¶

The program gives an HTTPS encrypted traffic packet, first getting the certificate from it.

➜  2017_SECCON_verysmooth git:(master) binwalk -e s.pcap

--------------------------------------------------------------------------------

2292          0x8F4           Certificate in DER format (x509 v3), header length: 4, sequence length: 467

4038          0xFC6           Certificate in DER format (x509 v3), header length: 4, sequence length: 467

5541          0x15A5          Certificate in DER format (x509 v3), header length: 4, sequence length: 467

➜ 2017_SECCON_verysmooth git: (master) ls
s.pcap  _s.pcap.extracted  very_smooth.zip


Here are three certificates, three modules are the same, only one example is given here.

➜  _s.pcap.extracted git:(master) openssl x509 -inform DER -in FC6.crt  -pubkey -text -modulus -noout

-----BEGIN PUBLIC KEY-----

8lohddAsi28qwMXCe2cDWuwZKzdB3R9NEnUxsHqwEuuGJBwJwIFJnmnvWurHjcYj
DUddp + 4X8C9jtvCaLTgd + baSjo2eB0f + uiSL / 9 / 4NN + vR3FliRm2mByeFCjppTQl
yioxCqbXYIMxGO4NcQIDAQAB
-----END PUBLIC KEY-----

Certificate:

Data:

Version: 1 (0x0)

Serial Number: 11640506567126718943 (0xa18b630c7b3099df)

Signature Algorithm: sha256WithRSAEncryption

Issuer: C=JP, ST=Kawasaki, O=SRL

Validity

Not Before: Oct  8 02:47:17 2017 GMT

Not After : Oct  8 02:47:17 2018 GMT

Subject: C=JP, ST=Kawasaki, O=SRL

Subject Public Key Info:

Public Key Algorithm: rsaEncryption

Public-Key: (1024 bit)

Modulus:

00:d5:46:aa:82:5c:f6:1d:e9:77:65:f4:64:fb:fe:

c5: c2: 7b: 67: 03: 5a: ec: 19: 2b: 37: 41: dd: 1f: 4d: 12:
75: 31: b0: 7a: b0: 12: eb: 86: 24: 1c: 09: c0: 81: 49: 9e:
69: ef: 5a: ea: c7: 8d: c6: 23: 0d: 47: 5d: a7: ee: 17: f0:
2f: 63: b6: f0: 9a: 2d: 38: 1d: f9: b6: 92: 8e: 8d: 9e:47: fe: ba: 24: 8b: ff: df: f8: 9c: df: af: 47: 71: 65: 89:
19: b6: 98: 1: 9e: 14: 28: e9: a5: 34: 25: ca: 2a: 31: 0a:
a6: d7: 60: 83: 31: 18: in: 0d: 71
Exponent: 65537 (0x10001)

Signature Algorithm: sha256WithRSAEncryption

78: 92: 11: fb: 6c: e1: 7a: f7: 2a: 33: b8: 8b: 08: a7: f7: 5b: de: cf:
62:0b:a0:ed:be:d0:69:88:38:93:94:9d:05:41:73:bd:7e:b3:

32:ec:8e:10:bc:3a:62:b0:56:c7:c1:3f:60:66:a7:be:b9:46:

f7:46:22:6a:f3:5a:25:d5:66:94:57:0e:fc:b5:16:33:05:1c:

6f:f5:85:74:57:a4:a0:c6:ce:4f:fd:64:53:94:a9:83:b8:96:

bf: 5b: a7: ee: 8b: 1e: 48: a7: d2: 43: 06: 0e: 4f: 5a: 86: 62: 69:
e2: c0: bd: 4e: 89: c9: af: 04: 4a: 77: a2:
b7: 39


It can be seen that the modulus is only 1024 bits. Moreover, according to the title name very smooth, it should be one of the factors comparing smooth, here we use the primaryfac to try Pollard's p − 1 and Williams's p + 1 algorithm respectively, as follows

➜  _s.pcap.extracted git:(master) python -m primefac -vs -m=p+1  149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897

149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897: p+1 11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 12684117323636134264468162714319298445454220244413621344524758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897

Z309  =  P155 x P155  =  11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 x 12684117323636134264468162714319298445454220244413621344524758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897


It can be found that when using the Williams's p + 1 algorithm, it is directly decomposed. It is reasonable to say that this factor is p-1 seems to be smoother, but it cannot be decomposed using the Pollard's p − 1 algorithm. Further testing is done here.

➜  _s.pcap.extracted git:(master) python -m primefac -vs 1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002

1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002: 2 7 43 503 761429 5121103123294685745276806480148867612214394022184063853387799606010231770631857868979139305712805242051823263337587909550709296150544706624823

Z154  =  P1 x P1 x P2 x P3 x P6 x P142  =  2 x 7 x 43 x 503 x 761429 x 5121103123294685745276806480148867612214394022184063853387799606010231770631857868979139305712805242051823263337587909550709296150544706624823

➜  _s.pcap.extracted git:(master) python -m primefac -vs 1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

Z154  =  P1^185 x P1^62 x P1^97  =  2^185 x 3^62 x 5^97


It can be seen that there are indeed many small factors for p-1, but the number is too large, which will cause an exponential explosion when enumerating, so it is not decomposed.

And construct a private key based on the decomposed number

from Crypto.PublicKey import RSA

import gmpy2

def main():

n = 149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897L

p = 11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001L

q = 12684117323636134264468162714319298445454220244413621344524758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897L

e = 65537L
priv = RSA.construct((n, e, long(gmpy2.invert(e, (p - 1) * (q - 1)))))

open('private.pem', 'w').write(priv.exportKey('PEM'))

main()


Finally, import the private key into wireshark to get the plain text (Edit -> Preferences -> Protocols -> SSL -> RSA Key List).

<html>

<body>

<h1>

Answer: One of these primes is very smooth.

</h1>

</body>

</html>


### Extension¶

For more on some methods of decomposing the modulus N, please refer to https://en.wikipedia.org/wiki/Integer_factorization.

## 模不素素¶

### Attack principle¶

When there are two public keys, N is not mutually prime, we can obviously obtain the greatest common factor directly for these two numbers, and then directly obtain p, q, and then obtain the corresponding private key.

### SCTF RSA2¶

Here we take SCTF rsa2 as an example. Open the pcap package directly and find that there are a bunch of messages, including N and e, and then try to test whether the different N is mutual. I tried the first two.

import gmpy2

n1 =
n2 =
print gmpy2.gcd(n1, n2)


The results found that they were not mutually exclusive.

➜  scaf-rsa2 git:(master) ✗ python exp.py

122281872221091773923842091258531471948886120336284482555605167683829690073110898673260712865021244633908982705290201598907538975692920305239961645109897081011524485706755794882283892011824006117276162119331970728229108731696164377808170099285659797066904706924125871571157672409051718751812724929680249712137


Then we can decrypt it directly, here we use the first pair of public key ciphers. code show as below

from Crypto.PublicKey import RSA

from Crypto.Cipher import PKCS1_v1_5, PKCS1_OAEP

import gmpy2

from base64 import b64decode

n1 =
n2 =
p1 = gmpy2.gcd(n1, n2)

q1 = n1 / p1

e = 65537
phin = (p1 - 1) * (q1 - 1)
d = gmpy2.invert (e, phin)

plain = gmpy2.powmod(cipher, d, n1)

plain = hex(plain)[2:]

if len (plain)% 2! = 0:
plain = '0' + plain

print plain.decode('hex')


Finally decrypted as follows

➜  scaf-rsa2 git:(master) ✗ python exp.py
sH1R3_PRlME_1N_rsA_iS_4ulnEra5le


Unzip the package.

## Common mode attack¶

### Attack conditions¶

When two users use the same modulus N and different private keys, there is a common mode attack when encrypting the same plaintext message.

### Attack principle¶

Let the public keys of the two users be $e_1$ and $e_2$, respectively, and they are mutually prime. The plain text message is $m$ and the ciphertext is:

$$c_1 = m ^ {} e_1 N \ way c_2 = m ^ {} e_2 N way$$

When the attacker intercepts $c_1$ and $c_2$, the plaintext can be recovered. Use the extended Euclidean algorithm to find the two integers $r$ and $s$ of $re_1+se_2=1\bmod n$, which gives you:

\begin{align*} c_{1}{r}c_{2}{s} &\equiv m{re_1}m{se_2}\bmod n\ &\equiv m^{(re_1+se_2)} \bmod n\ &\equiv m\bmod n \end{align*}

### XMan Phase I Summer Camp Classroom Exercise¶

Description of the topic:

{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,773}

{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,839}

message1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349

message2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535


> Source: XMan Summer Camp Class Exercise

It can be seen that the N of the two public keys are the same, and the e of the two are mutually prime. Write a script to run:

import gmpy2

n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249

e1 = 773

e2 = 839

message1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349

message2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535
# s & t

gcd, s, t = gmpy2.gcdext(e1, e2)

if s < 0:

s = -s

message1 = gmpy2.invert(message1, n)

if t < 0:

t = -t

message2 = gmpy2.invert(message2, n)

plain = gmpy2.powmod(message1, s, n) * gmpy2.powmod(message2, t, n) % n

print plain


get

➜  Xman-1-class-exercise git:(master) ✗ python exp.py

1021089710312311910410111011910111610410511010710511610511511211111511510598108101125


At this time, you need to consider how the plaintext was converted to this number, which is generally a hexadecimal conversion, ASCII character conversion, or Base64 decryption. This should be an ASCII character conversion, and then we use the following code to get the flag

i = 0

flag = ""

plain = str(plain)

while i < len(plain):

if plain[i] == '1':

flag += chr(int(plain[i:i + 3]))

i += 3

else:

flag += chr(int(plain[i:i + 2]))

i += 2

print flag


The reason why 1 is used to determine whether it is three-bit length is because the flag is usually a plain text character, and the number starting with 1 is 1 or 2, which is generally an invisible character.

flag

➜  Xman-1-class-exercise git:(master) ✗ python exp.py

flag{whenwethinkitispossible}


## topic¶

• Jarvis OJ very hard RSA