> Something about this randomly generated noise doesn't seem right...

We have a script

```python
from Crypto.Util.number import bytes_to_long, getStrongPrime
from fractions import gcd
from secret import flag
from Crypto.Random import get_random_bytes

def encrypt(number):
return pow(number,e,N)

def noisy_encrypt(a,m):
return encrypt(pow(a,3,N)+(m << 24))

e = 3
p = getStrongPrime(512)
q = getStrongPrime(512)

while (gcd(e,(p-1)*(q-1)) != 1):
p = getStrongPrime(512)
q = getStrongPrime(512)

N = p * q

print("N : " + str(N) + "\n")
print("e : " + str(e) + "\n")

rand = bytes_to_long(get_random_bytes(64))

ct = []
ct.append(encrypt(rand << 24))

for car in flag:
ct.append(noisy_encrypt(car,rand))

print(ct)
```

and its output

```
N : 166340340660877519226247260987065058211371932250499241074633026863387096385721863889904212902371869444274842128829082337552709506851212430322777753756706525557339442213042322434951929492350910439291882068704178535251621706072605607671593003649095340546077718624006859019891494745600258808326203381366558360403

e : 3

[72881243587279652525011668389480886731233379003340815331672052156449010464010693304931728042216088657642642153607136661251184626426811987027166068591298345434705349712743185809458404592395692720660113774009080627872192793713309891346264883115832358507857462312275400764420518834080531059771744334365221989634,
120942671498483330060520229769388972851903750065221974908980408800142585447054246279988215440838619341480941425987900671088263735178370517975791870374867924130327757712683134115691371457608477285865042459315287349798635279186783640977356463108475695769654664032379733434805748471608372219467852099247995100354,
...
]
```

There is a standard RSA encryption (with 1024 bit N and e=3) happening and some *noisy encryption* which mixes a 512 bit random number into the process. Or, to be precise, if `r` is that random number than

r' = r<<24 = r*2^24

is used.

We have the encryption of the flag's letters, character by character.

The noisy encryption works as follows:

First, the letter `a` is encrypted with normal RSA to

c = a^3 mod N

Then a second step follows to produce the output l (which we know from the list)

l = (c + r')^3 = c^3 + 3*c^2*r' + 3*c*r'^2 + r'^3

(all operations done modulo N). We know l and c for the first 7 ciphertexts (flag starts with `shkCTF{`). We also know `r'^3 mod N`, which is the first item in our list.

If we can calculate `r'`, we can simply encrypt all letters and reproduce the flag.

To get `r` we can do the following:

Build two of those equations above using the first two ciphertexts and our knowledge of `r'^3`. Treating the exponents of `r'` as independent variables we have a system of two linear modular equations in two variables which is solvable.

The following sage script can extract `r'`:

```
N=1663403406608775192262472609870650582113719322504992410746330268633870963857218638899042129023718694442748421288290823375527095068512124303227777537567065255573394422130423224349519\
29492350910439291882068704178535251621706072605607671593003649095340546077718624006859019891494745600258808326203381366558360403
e=3
R = 72881243587279652525011668389480886731233379003340815331672052156449010464010693304931728042216088657642642153607136661251184626426811987027166068591298345434705349712743185809458\
404592395692720660113774009080627872192793713309891346264883115832358507857462312275400764420518834080531059771744334365221989634
l1 = 1209426714984833300605202297693889728519037500652219749089804088001425854470542462799882154408386193414809414259879006710882637351783705179757918703748679241303277577126831341156\
91371457608477285865042459315287349798635279186783640977356463108475695769654664032379733434805748471608372219467852099247995100354
l2 = 5438672189546541565638095795090454973655647973802164622137861080471631141548748989051132531613614779730529847214191292711998177290923856962201124553373128198319134604628485939479\
0231772028252518442679512839637492607553340532809710322773811504243675887595893870027501332275699811129878490987811760210612933716

F = Zmod(N)

p1 = ord('s')
p2 = ord('h')
c1 = F(power_mod(p1, e, N))
c2 = F(power_mod(p2, e, N))

d1 = F(l1 - c1^3 - R)
k11 = F(3*c1^2)
k21 = F(3*c1)

d2 = F(l2 - c2^3 - R)
k12 = F(3*c2^2)
k22 = F(3*c2)

# k11*r + k21*r^2 == d1
# k12*r + k22*r^2 == d2
# ----------------------
# (k11*k22-k12*k21)*r == (d1*k22 - d2*k21)

a = k11*k22-k12*k21
b = d1*k22 - d2*k21
# a*r == b
r = b*a^(-1)
print(r)
#Sanity check
assert(k21*r^2+k11*r == d1)
assert(k22*r^2+k12*r == d2)
```

The value of `r'` is `16042760712376809922314266333387918695978347235657595682174901751357624863232775176277935114355575868431675512690546248845338838324374751844663435260133606686720`.

Now we just need to reconstruct the flag:

```python
from data import ciphertexts

r = 16042760712376809922314266333387918695978347235657595682174901751357624863232775176277935114355575868431675512690546248845338838324374751844663435260133606686720

chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ{}-_#0123456789"

N=1663403406608775192262472609870650582113719322504992410746330268633870963857218638899042129023718694442748421288290823375527095068512124303227777537567065255573394422130423224349519\
29492350910439291882068704178535251621706072605607671593003649095340546077718624006859019891494745600258808326203381366558360403
e=3

def encrypt(number):
return pow(number,e,N)

def noisy_encrypt(a):
return encrypt(pow(a,3,N)+r)

# Sanity check
assert(noisy_encrypt(ord('s')) == ciphertexts[0])
assert(noisy_encrypt(ord('h')) == ciphertexts[1])

# Build a dictionary of all ciphertexts
ctpt = {}
for char in chars:
ct = noisy_encrypt(ord(char))
ctpt[ct] = char

# Reconstruct the flag from the knows plaintext/ciphertext pairs
flag = ''
for ct in ciphertexts:
if(ct in ctpt):
flag += ctpt[ct]
else:
flag += "#"

print(flag)
```

(data.py just contains the array with the ciphertexts)

Flag: **shkCTF{L0NG_LIV3_N0ISY_RS4_b86040a760e25740477a498855be3c33}**