Xctf attack and defense world crypto advanced area best_ rsa

1. Enter the environment , Download the attachment

Compressed package for topic , Include 4 File , Pictured ：

given 2 Public key files and 2 Ciphertext file , With regular RSA Decryption methods: decrypt separately , Decryption failed （n by 2048 Bits are hard to decompose ）

2. Problem analysis

1. Continue to review RSA

• In plain text m, The secret is c, modulus n = p * q
• Use Euler functions ,φ(n) = (p - 1) * (q- 1)
• Select a large integer e, bring gcd(e, φ(n) ) = 1,e Used to encrypt the secret key
• Private key d It can be calculated from the value of Euler function , Satisfy ed mod φ(n) ≡ 1
• In plain text m Encrypted into ciphertext c：m^e ≡ c (mod n)
• Will ciphertext c Decrypt to plaintext m：c^d ≡ m (mod n)

2. Common mode attack
   Guess it should be the same plaintext , Used 2 Different public key encryption results in different ciphertexts , Using the same modulus and different public key indices for multiple encryption of the same plaintext may lead to common mode attacks .

Look at the boss's wp after ：https://blog.csdn.net/weixin_44795952/article/details/108933406, Understand what common mode attack is

So called common mode , Is plaintext m identical , model n identical , Use two public keys e1,e2 Encrypt to get two private keys d1,d2 And two ciphertexts c1,c2
Common mode attack , When n Without change , know n,e1,e2,c1,c2 . Can be in the don't know d1,d2 Under the circumstances , figure out m.
There's a condition , namely

gcd(e1,e2)=1

3. Attack principle
   There are integers $s_1$, $s_1$( One is one minus one. ）, Satisfy ：

$e_1\ast s_1+e_2\ast s_2=1$

from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from gmpy2 import gcd, invert


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


with open('pic/publickey1.pem', 'rb') as f:
    f1 = f.read()
pub1 = RSA.importKey(f1)

n = int(pub1.n)
e1 = int(pub1.e)

with open('pic/publickey2.pem', 'rb') as f:
    f2 = f.read()
pub2 = RSA.importKey(f2)

e2 = int(pub2.e)

with open('pic/cipher1.txt', 'rb') as f:
    c1 = f.read()
c1 = bytes_to_long(c1)
print(c1)

with open('pic/cipher2.txt', 'rb') as f:
    c2 = f.read()
c2 = bytes_to_long(c2)
print(c2)

print(gcd(e1, e2))
s = egcd(e1, e2)

s1 = s[1]
s2 = s[2]

if s1 < 0:
    s1 = -s1
    c1 = invert(c1, n)
elif s2 < 0:
    s2 = -s2
    c2 = invert(c2, n)

m = pow(c1, s1, n) * pow(c2, s2, n) % n
print(m)
print(long_to_bytes(m).decode())