Tags: crypto cryptography-rsa
Rating:
## PQ
- Tags: Crypto
- Description: Sup! I have a warm-up exercise for you. Test yourself!
## Solution
- To solve this question you need to download the two files and open them. One contains a script, another contains an output after encryption process.
- This is a RSA encryption. RSA is a type of asymmetric encryption, which uses two different but linked keys. In RSA cryptography, both the public and the private keys can encrypt a message. The opposite key from the one used to encrypt a message is used to decrypt it.
```
from secret import flag
import gmpy2
import os
e = 65537
def generate_pq():
seed_1 = os.urandom(256)
seed_2 = os.urandom(128)
p = gmpy2.next_prime(int.from_bytes(seed_1, 'big'))
q = gmpy2.next_prime(p + int.from_bytes(seed_2, 'big'))
return p, q
def crypt(text: bytes, number: int, n: int) -> bytes:
encrypted_int = pow(int.from_bytes(text, 'big'), number, n)
return int(encrypted_int).to_bytes(n.bit_length() // 8 + 1, 'big').lstrip(b'\x00')
def decrypt(ciphertext: bytes, d: int, n: int) -> bytes:
decrypted_int = pow(int.from_bytes(ciphertext, 'big'), d, n)
return int(decrypted_int).to_bytes(n.bit_length() // 8 + 1, 'big').lstrip(b'\x00')
if __name__ == '__main__':
p, q = generate_pq()
N = p * q
print(N)
print(crypt(flag, e, N))
```
- We don't know the "p" and "q" because they are random, so we have to find them using "sympy" Python library.
```
import sympy
number = 132086762100302078158612307179906631909898806981783638872466068002300869623098630620165448768720254883137327422672476805043691480174256036180721731497587237715063454297790495969483489207136972250164710188420225763233747908701283027078438344664299014808416413571351542599081752555686770028413716796078873813330590445832860793314759609313764623765380933591724606330437910835716715531622488954094537786597047153926251039954598771799135047290146418281385535642767911286195336847939581845201323419481454339068278410371643803608271670287022348951939900020976969310691364928577827628933372033862233255290645770491410483896580775901424709960774246239786459897154645326725577247495081862202329964850883099304655731249899682207929191809089102784910271194419106763854156131659154288130473334913716310774837544357552145818946965762232701773929485120822084798271812866558958017482859639309145534006213755797867458114047179151432620199901531647274556045226842412846249745453829411110791389589361083639248497794972860374118825453789815945054941317357362356097204626302358978602557740022604702272869574989276916907973619219179668721219956360339907020399117153780337123055361243263164411540233136750115943236824586938269115081034357185003848577647497
prime_factors = sympy.factorint(number)
print(prime_factors)
```
- From this we find prime factors that can help us to find "d".
```
p = 11492900508587989954531440332263108922084741581974222102472118047768380430540353920289746766137088552446667728704705825767564907436992191013818658710263387461050109924538094327413211095570408951831804511312664061115780934181616871945218328272318074413219648490794574757471025686956697500105383560452507555043577475707379430674941097523563439495291391376433292863780301364692520578080638180885760050174506019604723296382744280564071968270446660250234587067991312783613649361373626181634408704506324790573495089018767820926445333763821104985493381745364201010694528200379210559415841578043670235152463040761395093466757
q = 11492900508587989954531440332263108922084741581974222102472118047768380430540353920289746766137088552446667728704705825767564907436992191013818658710263387461050109924538094327413211095570408951831804511312664061115780934181616871945218328272318074413219648490794574757471025686956697500105383560452507555043583332241787496934511124508164581479242699938954664986778778089174462752116916848703843649899098070668669678312274875686923774909987821333120312320645501581685293243247702323898532381890355435523179413889042894904950054113266062322984191234608909924029167449813744492456171898301189923726970620918920525920821
N = 132086762100302078158612307179906631909898806981783638872466068002300869623098630620165448768720254883137327422672476805043691480174256036180721731497587237715063454297790495969483489207136972250164710188420225763233747908701283027078438344664299014808416413571351542599081752555686770028413716796078873813330590445832860793314759609313764623765380933591724606330437910835716715531622488954094537786597047153926251039954598771799135047290146418281385535642767911286195336847939581845201323419481454339068278410371643803608271670287022348951939900020976969310691364928577827628933372033862233255290645770491410483896580775901424709960774246239786459897154645326725577247495081862202329964850883099304655731249899682207929191809089102784910271194419106763854156131659154288130473334913716310774837544357552145818946965762232701773929485120822084798271812866558958017482859639309145534006213755797867458114047179151432620199901531647274556045226842412846249745453829411110791389589361083639248497794972860374118825453789815945054941317357362356097204626302358978602557740022604702272869574989276916907973619219179668721219956360339907020399117153780337123055361243263164411540233136750115943236824586938269115081034357185003848577647497
e = 65537
phi = (p-1) * (q-1)
def egcd(a, b):
if a == 0:
return (b, 0, 1)
g, y, x = egcd(b%a,a)
return (g, x - (b//a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('No modular inverse')
return x%m
d = modinv(e, phi)
print('D = ', d)
```
- After we find all of the arguments and pieces for the "decrypt()" function, now we can use it and get the flag.
```
VolgaCTF{0x8922165e83fa29b582f6a252cb337a05}
```
