Tags: rsa-crypto
Rating:
# Sign me up
## Description
> Alice and Bob like to send each other encrypted messages. Eve intercepted one of those messages but doesn't know what to do with it.
>
> She knows that Bob's public key is (n,e) = (20312493432722984634615913227523125265781662152013094377607630781356105942700273581600613724248110835803158659086732527322062709047441686884292861771528866639670389435647460159612029672461252955594829829663172687201461554413049025271464412190235617740846789840419025423396967519520427432799227162339126087426790939948330768088600429869826069490486741417370162186831426441346576810446894902659826134877586519596679449287778809427232767231366708775004671368581690484301650399106765403344734339945464967775820750215294237822308697430395972800155973323880641007064174229976873404987801414040860359400339131120435868680687, 65537)
>
> You can download the file they were given at the following link: https://drive.google.com/file/d/1hLMbGIcHtZztIpo8t-6gbZryhnJcG1QH/view?usp=sharing
The file contains the following:
```
[2412288710434803394325176302030468602332709509311261143213660105436051377474943434821352204391721838391094315381960457432926655230840188063004267704110217562996169458737321422147946731024824906666581789481224658816667320712242183812495582365431358466421457338958297482318446752036156998046759116584692778102962227510956304634319673372386442935449493449571951014061135438098777831213738694319264871993054355739648850198401208660679119608287231277223330049800856485854048034076593360115933185266555106462189543603546500451391092789804740311728163218531654743934699161954489811160497924455252382430259665344226005589347, 4662244614481813573605424119126644876253617822761086977288944256748253172049152895283835285197942460107100639460725911487653228318143490793643886766659418932464516271704300924229817717506546624597745450582808476115888422680291782220162004150600402753933990809607808329788541808351295733460528312120185127926061134106046844047543905543159332742611020978955776656246495124585638018893950754232515884963378422307924949629539205551516343049930064201297659168924875147225592455456266529935523931058354274895303194139310196368597695032712292358385042137122599970681963372287225693772146511056611914691897651969859481791738, 12063404184597232404323191243850651767007295266547011829578075758182531208671092480607343538388450277669022734103195085335379453509513928281873248621822304221535910976898189043438151642195662401534323194805294363709940776238048702852641738949402011411364230898498892721433997197353442189049609705253970415482575225470252945036637259407162734288203452962405448110624034513372135117708937804305185686067759553911606385985218168514851708713854774534268652136104206983382772232368346294401708885399333595608729871189892495869786648151489184098357431988262435191288083393719085655077650503402400856646850476286449510347919, ...]
```
(the end of the file is not displayed).
## Solution
We recognize a RSA encrypted message.
Contrary to the challenge `Pretty Ridiculous`, it seems unlikely we'll be able to factorize `n`.
However the ciphertext is in a particular way: instead of having the whole message encoded as one integer, it seems that every character is encrypted one by one... Let's check this: first character is supposed to be `a` because of the flag format, so let's compute `97 ^ e mod n`: it matches our first number in the file (`97` is the ASCII encoding of `a`).
Therefore we can just encrypt every ASCII character and compare them with our ciphertext! Let's do this with Python:
```python
N = 20312493432722984634615913227523125265781662152013094377607630781356105942700273581600613724248110835803158659086732527322062709047441686884292861771528866639670389435647460159612029672461252955594829829663172687201461554413049025271464412190235617740846789840419025423396967519520427432799227162339126087426790939948330768088600429869826069490486741417370162186831426441346576810446894902659826134877586519596679449287778809427232767231366708775004671368581690484301650399106765403344734339945464967775820750215294237822308697430395972800155973323880641007064174229976873404987801414040860359400339131120435868680687
e = 65537
with open(file, 'r') as f:
sinit = f.readlines()[0]
s = sinit[1:-1]
list_char = s.split(',')
dic = {}
for i in range(33, 300):
code = i**e % N
dic[code] = chr(i)
ans = ''
for c in list_char :
ans += dic[int(c)]
print(ans)
```
Flag: `auctf{D0nT_5igN_r4nd0m_Cr4P_w1tH_y0uR_pr1vAT3_k3y_d00d}`
