# PicoCTF 2017 - Crypto Challenges

Datetime:2017-04-20 05:32:59         Topic: Encryption and Decryption          Share        Original >>

So, here's my first set of Pico solutions. I've started with the crypto for now. For those of you who don't fancy reading through, here are some links to each one.

## Keyz

This one's trivial. Run `ssh-keygen` , `cat ~/.ssh/id_rsa.pub` and copy the public key, then in the web shell, `mkdir .ssh; echo "[public key]" > ~/.ssh/authorized_keys`

Then, just ssh in and the flag's in the MOTD

Flag: `who_needs_pwords_anyways`

## Substitute

`A wizard (he seemed kinda odd...) handed me this. Can you figure out what it says?`

This one is also pretty trivial. Looking at the message, and the name of the challenge, just guess that it's a simple substitution cipher. Take the ciphertext you're given, and paste it into quipqiup . A few moments later, you get the flag

Flag: `IFONLYMODERNCRYPTOWASLIKETHIS`

## Hash101

This one consists of four separate levels.

```Welcome to Hashes 101!

There are 4 Levels. Complete all and receive a prize!

-------- LEVEL 1: Text = just 1's and 0's --------
All text can be represented by numbers. To see how different letters translate to numbers, go to http://www.asciitable.com/

TO UNLOCK NEXT LEVEL, give me the ASCII representation of 0110100001100101011011000110110001101111```

For this one, just convert the binary through to ASCII however you like. It turns out to be `hello`

The next level is just as easy:

```------ LEVEL 2: Numbers can be base ANYTHING -----
Numbers can be represented many ways. A popular way to represent computer data is in base 16 or 'hex' since it lines up with bytes very well (2 hex characters = 8 binary bits). Other formats include base64, binary, and just regular base10 (decimal)! In a way, that ASCII chart represents a system where all text can be seen as "base128" (not including the Extended ASCII codes)

TO UNLOCK NEXT LEVEL, give me the text you just decoded, hello, as its hex equivalent, and then the decimal equivalent of that hex number ("foo" -> 666f6f -> 6713199)

hex>```

Convert "hello" to hex, and you get `68656c6c6f`

```hex>68656c6c6f
Good job! 68656c6c6f to ASCII -> hello is hello
Now decimal
dec>```

Convert `0x68656c6c6f` to decimal, and you get `448378203247`

The next level introduces a simple modular hash function.

```----------- LEVEL 3: Hashing Function ------------
A Hashing Function intakes any data of any size and irreversibly transforms it into a fixed-length number. For example, a simple Hashing Function could be to add up the sum of all the values of all the bytes in the data and get the remainder after dividing by 16 (modulus 16)

TO UNLOCK NEXT LEVEL, give me a string that will result in a 0 after being transformed with the mentioned example hashing function

>```

In this case, the hash function on a single character c is simply `c % 0x10` . Therefore, let's just use 0x50, or `E`

One more level....

```--------------- LEVEL 4: Real Hash ---------------
A real Hashing Function is used for many things. This can include checking to ensure a file has not been changed (its hash value would change if any part of it is changed). An important use of hashes is for storing passwords because a Hashing Function cannot be reversed to find the initial data. Therefore if someone steals the hashes, they must try many different inputs to see if they can "crack" it to find what password yields the same hash. Normally, this is too much work (if the password is long enough). But many times, people's passwords are easy to guess... Brute forcing this hash yourself is not a good idea, but there is a strong possibility that, if the password is weak, this hash has been cracked by someone before. Try looking for websites that have stored already cracked hashes.

TO CLAIM YOUR PRIZE, give me the string password that will result in this MD5 hash (MD5, like most hashes, are represented as hex digits):

Just look up the hash on any of the myriad hash lookup services . In this case, the hash is of `3mb0x` . So, finally, we get our flag!

```Correct! Completed level 4
You completed all 4 levels! Here is your prize: c3ee093f26ba147ccc451fd13c91ffce```

Flag: `c3ee093f26ba147ccc451fd13c91ffce`

## ComputeAES

We get the following info:

```Encrypted with AES in ECB mode. All values base64 encoded
ciphertext = rW4q3swEuIOEy8RTIp/DCMdNPtdYopSRXKSLYnX9NQe8z+LMsZ6Mx/x8pwGwofdZ
key = 6v3TyEgjUcQRnWuIhjdTBA==```

So, we open up a python REPL:

```>>> from Crypto.Cipher import AES
>>> from base64 import b64decode
>>> cipher = AES.AESCipher(b64decode("6v3TyEgjUcQRnWuIhjdTBA=="), AES.MODE_ECB)
>>> print cipher.decrypt(b64decode("rW4q3swEuIOEy8RTIp/DCMdNPtdYopSRXKSLYnX9NQe8z+LMsZ6Mx/x8pwGwofdZ"))
flag{do_not_let_machines_win_983e8a2d}_________```

Oooh, look, a flag.

Flag: `flag{do_not_let_machines_win_983e8a2d}`

## ComputeRSA

Also trivial.

`RSA encryption/decryption is based on a formula that anyone can find and use, as long as they know the values to plug in. Given the encrypted number 150815, d = 1941, and N = 435979, what is the decrypted number?`
```>>> pow(150815, 1941, 435979)
133337L```

Flag: `133337`

## SoRandom

```We found sorandom.py running at shell2017.picoctf.com:33123. It seems to be outputting the flag but randomizing all the characters first. Is there anyway to get back the original flag?
Update (text only) 16:16 EST 1 Apr Running python 2 (same version as on the server)```

First of all, let's take a look at the server code:

```#!/usr/bin/python -u
import random,string

encflag = ""
random.seed("random")
for c in flag:
if c.islower():
#rotate number around alphabet a random amount
encflag += chr((ord(c)-ord('a')+random.randrange(0,26))%26 + ord('a'))
elif c.isupper():
encflag += chr((ord(c)-ord('A')+random.randrange(0,26))%26 + ord('A'))
elif c.isdigit():
encflag += chr((ord(c)-ord('0')+random.randrange(0,10))%10 + ord('0'))
else:
encflag += c
print "Unguessably Randomized Flag: "+encflag```

So, it's generating a fixed "rotated" alphabet, based on a PRNG with a known seed. We can generate the inverse of this shift by simply replacing `+` with `-` , then pull the scrambled flag from the server. This leads us to the following:

```#!/usr/bin/python -u
import random,string

flag = "BNZQ:2m8807395d9os2156v70qu84sy1w2i6e"
encflag = ""
random.seed("random")
for c in flag:
if c.islower():
#rotate number around alphabet a random amount
encflag += chr((ord(c)-ord('a')-random.randrange(0,26))%26 + ord('a'))
elif c.isupper():
encflag += chr((ord(c)-ord('A')-random.randrange(0,26))%26 + ord('A'))
elif c.isdigit():
encflag += chr((ord(c)-ord('0')-random.randrange(0,10))%10 + ord('0'))
else:
encflag += c
print "Unguessably Randomized Flag: "+encflag```

Run it, and we get a flag.

Flag: `FLAG:9b6098160b2ca5139c83fe29fd7c9e5d`

## LeakedHashes

`Someone got hacked! Check out some service's password hashes that were leaked at hashdump.txt! Do you think they chose strong passwords? We should check... The service is running at shell2017.picoctf.com:3815!`

Download the hash list that we're given, and run hashcat against it:

`hashcat64 -a 0 -m 0 --username pico.txt rockyou.txt`

Now show us the results, and see if we've cracked anything...

```E:\Users\Ben\Documents\hashcat-3.20>hashcat64 -a 0 -m 0 --username pico.txt rockyou.txt --show
roselyn:189dbb843e5420471ba9f10f03d8e9dc:m0n3y```

So now we have creds `roselyn:m0n3y` . Use those to log into the service, and hit `y` . You'll get a bunch of ASCII art cats, and a flag somewhere amongst them.

Flag: `4f36a002cc953e6567a878758abc8cf9`

## Weird RSA

`We recovered some data. It was labeled as RSA, but what in the world are "dq" and "dp"? Can you decrypt the ciphertext for us?`

Okay, we're given some RSA parameters, including a "dp" and "dq". A little research reveals that those are used in a fast algorithm for RSA decryption based on the Chinese Remainder Theorem. These are our parameters:

```c = 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885
p = 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243
q = 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629
dp = 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961
dq = 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659```

So, we find a nice guide on how to use them, go off, and do just that.

Flag: `Theres_more_than_one_way_to_RSA`

## HashChain

`We found a service hiding a flag! It seems to be using some kind of MD5 Hash Chain authentication to identify who is allowed to see the flag. Maybe there is a flaw you can exploit? hcexample.py has some example code on how to calculate iterations of the MD5 hash chain. Connect to it at shell2017.picoctf.com:50102!`

So, this is a simple hash chain authentication scheme, where we authenticate by finding the hash in the chain prior to the "challenge" hash presented by the server. On connecting to the service, we are presented with the following options:

```*******************************************
***            FlagKeeper 1.1           ***
*  now with HASHCHAIN AUTHENTICATION! XD  *
*******************************************

Would you like to register(r) or get flag(f)?

r/f?```

Let's have a look at the registration...

```r
Hello new user! Your ID is now 9831 and your assigned hashchain seed is a62dd1eb9b15f8d11a8bf167591c2f17
Please validate your new ID by sending the hash before this one in your hashchain (it will hash to the one I give you):
7487f1eb2ff4cd1f60326ff74e1728a7```

Hmmm, that hashchain seed looks a lot like an MD5 hash in and of itself. Could it simply be the hash of the user ID?

`md5("9831") = a62dd1eb9b15f8d11a8bf167591c2f17`

That's a yes. Now, let's look at the get flag option...

```f
This flag only for user 8886
58a116a80bcdb2ed23423a49f5bfaabd
Next token?```

So, we can use the provided hc_example.py with a seed of "8886" to generate a bunch of hashes and see when `58a116a80bcdb2ed23423a49f5bfaabd` comes up.

```...
40249f4dcc725e5baf3cd6f959243273
58a116a80bcdb2ed23423a49f5bfaabd
...```

So, our next token is `40249f4dcc725e5baf3cd6f959243273` . Giving that to the service gives us our flag!

Flag: `96630f954dd403c7882666b5443e4678`

`You stumbled upon a group Message. Can you figure out what they were sending? The string sent is ASCII encoded as a hex number (submit the ASCII string as the flag)`

We use Håstad's broadcast attack (Clue's in the name). This attack is applicable where multiple messages are encrypted with the same `e` and different `n` , and allows us to leak the message without knowledge of `d` . Using this algorithm will output the flag.

Flag: `broadcast_with_small_e_is_killer_26528074390`

## SmallRSA

`You intercepted a single message. However, it appears to be encrypted. Can you decrypt it?`

First off, let's look at the information we have:

```e = 165528674684553774754161107952508373110624366523537426971950721796143115780129435315899759675151336726943047090419484833345443949104434072639959175019000332954933802344468968633829926100061874628202284567388558408274913523076548466524630414081156553457145524778651651092522168245814433643807177041677885126141
n = 380654536359671023755976891498668045392440824270475526144618987828344270045182740160077144588766610702530210398859909208327353118643014342338185873507801667054475298636689473117890228196755174002229463306397132008619636921625801645435089242900101841738546712222819150058222758938346094596787521134065656721069
c = 60109758698128083867894286068285517856121577775873732971271767838094375540242140682860856525076716857853484762310661349595705965454241788627490154678487289327504291223547525832864143253412180183596307295520420578906308624860023542143928885210079178897416418810270090406582415840515326539954964020452551186119```

That `e` value is unusually large, where you'd usually something like `e = 65537` . This suggests that `d` is quite small - hence the name of the challenge, probably. In this case, we can use Wiener's Attack to efficiently find the decryption key, `d` .

Using the attack, then, easily gets us `d` and allows us to decrypt the flag.

Flag: `flag{Are_any_RSA_vals_good_13441315963}`

## SmallSign

```This service outputs a flag if you can forge an RSA signature!
nc shell2017.picoctf.com 10650
smallsign.py```

So, some sort of a signature forging challenge. Let's look at the server code, for starters.

```#!/usr/bin/python -u

from Crypto.PublicKey import RSA
import random
import signal

key = RSA.generate(2048)

print "You have 60 seconds to forge a signature! Go!"
# In 60 seconds, deliver a SIGALRM and terminate
signal.alarm(60)

print "N:", key.n
print "e:", key.e

while True:
m = int(raw_input("Enter a number to sign (-1 to stop): "))
if m == -1:
break
sig = key.sign(m, None)
print "Signature:", str(sig[0])

challenge = random.randint(0, 2**32)
print "Challenge:", challenge
s = int(raw_input("Enter the signature of the challenge: "))
if key.verify(challenge, (s, None)):
print "Congrats! Here is the flag:", flag
else:
print "Nope, that's wrong!"```

So, we can get signatures for arbitrary numbers, and then submit a signature, given known (per attempt) values of `n` and `e` . In order to forge the signature, then, we rely on the fact that RSA encryption and decryption is multiplicative - that is:

`decrypt(m1) * decrypt(m2) % N = decrypt(m1 * m2)`

This leads us to the following process:

• Sign a bunch of the first few primes - as many as the 60-second limit allows.
• Factorise the challenge
• Pray to RNGesus that the prime factors of the challenge only include those which we've signed. If that's not the case, then try again.
• Compute the signature using the multiplicative property by multiplying the signatures of all the prime factors
• Submit result
• Get flag

I implemented this really rather inelegantly, but eh, it worked. This one, in particular, can take a long time to run - it relies on the RNG generating a challenge with small enough factors, and takes ~1min per run.

```import socket
def factor(n, startFrom=2):
"""returns a list of prime factors of n,
knowing min possible >= startFrom."""
if n <= 1:  return [ ]
d = startFrom
factors = [ ]
while n >= d*d:
if n % d == 0:
factors.append(d)
n = n/d
else:
d += 1 + d % 2  # 2 -> 3, odd -> odd + 2
factors.append(n)
return factors

def listPrimes(n):
'''Return a list of all primes < n using the Sieve of Eratosthenes.'''
if n <= 2:  return []
sieve = [True]*n # indices 0 ... n-1, ignore 1 and even.  Entries at odd
#  indices greater than 2 will be changed to false when found not prime
primes = [2]
i = 3
while(i < n):
if sieve[i]:  # First number not eliminated must be prime
primes.append(i)      # next eliminate multiples of i:
for mult in range(i*i, n, i): # Note multiples with a smaller
sieve[mult] = False       #   factor are already eliminated
i += 2  # skip even numbers
return primes

primes = listPrimes(1050)
def attempt():
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('shell2017.picoctf.com', 10650))
s.recv(1024)
d = s.recv(1024).split('\n')
n = int(d[1][3:])
e = int(d[2][3:])
sigs = {}
for prime in primes:
s.send(str(prime) + "\n")
s.recv(1024)
sigs[prime] = int(s.recv(1024).split('\n')[0])
s.send("-1\n")
s.recv(1024)
challenge = int(s.recv(1024).split('\n')[0])
f = factor(challenge)
rt = 1
for fact in f:
if fact in sigs:
rt = (rt * sigs[fact]) % n
else:
print "FAIL - No signature for %d" % fact
return False
s.send(str(rt) + "\n")
print s.recv(1024)
print s.recv(1024)
print s.recv(1024)
print s.recv(1024)
return True
r = False
while r == False:
r = attempt()```

Eventually, this gives us the flag.

Flag: `6298123dbccaf021eed3c55c79a806a3`

## Encrypted Shell

```This service gives a shell, but it's password protected! We were able intercept this encrypted traffic which may contain a successful password authentication. Can you get shell access and read the contents of flag.txt?
The service is running at shell2017.picoctf.com:30754.```

First off, let's start by looking at the server code so that we have an idea of what the hell we're dealing with here.

```#!/usr/bin/python2 -u
from hashlib import sha256
from Crypto import Random
from Crypto.Random import random
from Crypto.Cipher import AES
from subprocess import check_output, STDOUT, CalledProcessError

BLOCK_SIZE = 16
R = Random.new()

with open("parameters.txt") as f:

o = BLOCK_SIZE - len(m) % BLOCK_SIZE
return m + o * chr(o)

return p[0:-ord(p[-1])]

def send_encrypted(KEY, m):
aes = AES.new(KEY, AES.MODE_CBC, IV)
print (IV + c).encode('hex')

data = raw_input("").decode('hex')
IV, data = data[:BLOCK_SIZE], data[BLOCK_SIZE:]
aes = AES.new(KEY, AES.MODE_CBC, IV)
return m

def serve_commands(KEY):
while True:
try:
output = check_output(cmd, shell=True, stderr=STDOUT)
except CalledProcessError as e:
output = str(e) + "\n"
send_encrypted(KEY, output)

print """Welcome to the
______ _   _   _____ _          _ _
|  _  \ | | | /  ___| |        | | |
| | | | |_| | \ `--.| |__   ___| | |
| | | |  _  |  `--. \ '_ \ / _ \ | |
| |/ /| | | | /\__/ / | | |  __/ | |
|___/ \_| |_/ \____/|_| |_|\___|_|_|
"""

print "Parameters:"
print "p = {}".format(p)
print "g = {}".format(g)

a = random.randint(1, 2**46)
A = pow(g, a, p)
print "A = {}".format(A)

B = int(raw_input("Please supply B: "))
K = pow(B, a, p)

KEY = sha256(str(K)).digest()

serve_commands(KEY)
else:

So, basically, it performs a Diffie-Hellman Key Exchange and then authenticates via a password. Therefore, presumably, we need to follow a plan of attack something like:

• Break the Diffie-Hellman exchange in the traffic capture to get the shared key
• Connect to the server, exchange keys and authenticate with the password
• `cat flag.txt`

In order to do the first part, we'll need to calculate the discrete logarithm of one of the public values A or B modulo P. Fortunately, there appear to be some weak choices of parameter...

`a = random.randint(1, 2**46)`

This known, small bound on the value of `a` allows us to use the Baby-Step Giant-Step algorithm to compute the discrete logarithm of `A` fairly quickly and recover `a` . Let's look at the code.

```import gmpy
from gmpy import mpz

# Inputs to the algorithm
p=mpz([p from pcap])
g=mpz([g from pcap])
h=mpz([A from pcap])

hTable = {}

def main():
i = mpz(0)
j = mpz(0)
gI = gmpy.invert(g,p)
B = pow(2,23)
gC = pow(g,B,p)
while i <= B:
hTable[(h * pow(gI, i, p)) % p]=i
i = i + 1
print "Hash table created!"
while j <= B:
rhs = pow(gC, j, p)
if rhs in hTable:
i=hTable[rhs]
break
j = j + 1
print "Result: ",i,j,j*B+i

if __name__ == "__main__":
main()```

After a few minutes, this spits out our discrete logarithm. We now know that `a = 18999223985004`

With this knowledge, it's trivial to find our private key, and then our password:

```from hashlib import sha256
from Crypto import Random
from Crypto.Random import random
from Crypto.Cipher import AES
g = 41899070570517490692126143234857256603477072005476801644745865627893958675820606802876173648371028044404957307185876963051595214534530501331532626624926034521316281025445575243636197258111995884364277423716373007329751928366973332463469104730271236078593527144954324116802080620822212777139186990364810367977
a = 18999223985004
gb = 52212067689594112109323640929301351606467118203383150327599211883168430054342124696361946771882317563613814253170561126339826644357001686458446188458014200762135544004281320619787980315833659890517041361133454035724795056335268420608527814057585862519036050687522158793940953574062642063690400491833858296879
p = 174807157365465092731323561678522236549173502913317875393564963123330281052524687450754910240009920154525635325209526987433833785499384204819179549544106498491589834195860008906875039418684191252537604123129659746721614402346449135195832955793815709136053198207712511838753919608894095907732099313139446299843
K = pow(gb, a, p)
R = Random.new()
key=sha256(str(K)).digest()
BLOCK_SIZE = 16

return p[0:-ord(p[-1])]

data = data.decode('hex')
IV, data = data[:BLOCK_SIZE], data[BLOCK_SIZE:]
aes = AES.new(KEY, AES.MODE_CBC, IV)
return m

print passwd```

Let this run through, and we get the password: `ThisIsMySecurePasswordPleaseGiveMeAShell`

Finally, we need to get through those last couple of stages to get our flag. Let's write a simple client up.

```import socket
from hashlib import sha256
from Crypto import Random
from Crypto.Random import random
from Crypto.Cipher import AES
from subprocess import check_output, STDOUT, CalledProcessError

BLOCK_SIZE = 16
R = Random.new()
s = socket.socket()
o = BLOCK_SIZE - len(m) % BLOCK_SIZE
return m + o * chr(o)
return p[0:-ord(p[-1])]
def send_encrypted(KEY, m):
aes = AES.new(KEY, AES.MODE_CBC, IV)
out = (IV + c).encode('hex')
s.send(out + "\n")

data = data.decode('hex')
IV, data = data[:BLOCK_SIZE], data[BLOCK_SIZE:]
aes = AES.new(KEY, AES.MODE_CBC, IV)
return m
r = s.recv(1)
while msg not in r:
r += s.recv(1)
return r

s.connect(("shell2017.picoctf.com", 30754))
for _ in xrange(9):
s.recv(64)
b = 2
B = pow(g, b, p)
s.send(str(B) + "\n")
KEY = sha256(str(pow(A, b, p))).digest()
send_encrypted(KEY, "cat flag.txt\n")

Run this, and we get our flag back.

Flag: `908bf62fb191fd53a6a91e21774b8e7a`

## ECC2

```More elliptic curve cryptography fun for everyone!
handout.txt
(Yes, the flag will just be the number n.)```

Okay, an ECC challenge. I don't know much about ECC...

```Elliptic Curve: y^2 = x^3 + A*x + B mod M
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = *You can figure this out with the point below :)*

P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
n = *SECRET*
n*P = (84451374362414055424313800316751686580646332049899422670338102989180879521718, 43738739399518925611438079326671646924823599185742673040934524615350311254357)

n < 400000000000000000000000000000

Find n.```

Ah, that makes things a little clearer. Firstly, let's find B. It's but a simple python script away, as per usual.

```M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)

lhs = (P[1] ** 2) % M
rhs = (P[0] ** 3) + (P[0] * A) % M
print "B = %d" % ((lhs - rhs) % M)

B = 25255205054024371783896605039267101837972419055969636393425590261926131199030```

Okay, so now we have all of our curve parameters, we still need to find the value of n. In order to do this, we'll need to discover a little bit more information about our curve. One important property of the curve is the order of the generator point P. If it's smooth, we can reduce the problem into much smaller and more easily manageable ECDLPs and use the Chinese Remainder Theorem to combine these into our final value of `n` . This process is the Pohlig-Hellman Algorithm.

In order to test that, we'll use SageMath, which will be the tool of choice from here on. The code is stil quite brief:

```q = 93556643250795678718734474880013829509320385402690660619699653921022012489089
F = GF(q)
E = EllipticCurve(F, [66001598144012865876674115570268990806314506711104521036747533612798434904785,25255205054024371783896605039267101837972419055969636393425590261926131199030])
P = E(56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
Q = E(84451374362414055424313800316751686580646332049899422670338102989180879521718, 43738739399518925611438079326671646924823599185742673040934524615350311254357)
print factor(P.order())

2^2 * 3 * 5 * 7 * 137 * 593 * 24337 * 25589 * 3637793 * 5733569 * 106831998530025000830453 * 1975901744727669147699767```

Now, this does look quite interestingly smooth, so maybe Pohlig-Hellman is a good algorithm to use. However, those last two factors, in particular, look very large compared to the rest, so they'll probably add a vast amount to the computation time required. As this is a CTF, they're not going to make it take that much compute time, so we simply hand-wave and ignore those two factors. This leads us to the following code:

```def pohlig_hellman(curve, G, H):
N = curve.order()
factors = factor(N)[:-2]
x = 0
y = 1
for i in range(len(factors)):
ni = factors[i][0]**(factors[i][1])
y *= ni
tmp = N//ni
G_prime = tmp * G
H_prime = tmp * H
x_prime = G_prime.discrete_log(H_prime)
(gcd, x0, x1) = xgcd(ni, tmp)
x += x_prime*x1*tmp
return x % y

q = 93556643250795678718734474880013829509320385402690660619699653921022012489089
F = GF(q)
E = EllipticCurve(F, [66001598144012865876674115570268990806314506711104521036747533612798434904785,25255205054024371783896605039267101837972419055969636393425590261926131199030])
P = E(56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
Q = E(84451374362414055424313800316751686580646332049899422670338102989180879521718, 43738739399518925611438079326671646924823599185742673040934524615350311254357)
print factor(P.order())
s = pohlig_hellman(E, P, Q)

print "Is this correct? " + repr(P * s == Q)
print s

2^2 * 3 * 5 * 7 * 137 * 593 * 24337 * 25589 * 3637793 * 5733569 * 106831998530025000830453 * 1975901744727669147699767
Is this correct? True
300455670009368164962892984010```

The value of `n` , our flag, is that last number, and it is verified by the script.

Flag: `300455670009368164962892984010`

## Weirder RSA

`Another message encrypted with RSA. It looks like some parameters are missing. Can you still decrypt it? Message`

Missing parameters. How interesting. Let's see what we've got...

```e = 65537
n = 352758655756163603130656475864162239004344663459120398951306959672239055329877644796995008368282924624780849432051543118959312685532106237568240835778731486989439626252834661294225426875963944816709371554839452465119058016363040631618359944564550348310851045841670935254841385590882490443247265126417117450357
dp = 13530055667815347122266109008252377134325151556131892235929064596659462917644020624855537451062167377041847601387880412738836767351591511886432133011921729
c = 23428056833770750219439218340180501853506449797628734848807388355447212714387039203998085387476974936419607861041793755542930286287098871510394661091846780839592290953853536571372997807697657464569729651718518301857979495046280018444198435962234642736892075369840282923945267377104440625478468507147243879631```

Okay, so it's CRT-RSA without `dq` or `qinv` . That means we can't decrypt straight off. Fortunately, a little google finds us a paper with a key recovery method that lets us factorise n and thus find the decryption key. Let's throw something together...

```from fractions import gcd

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)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m

e = 65537
n = 352758655756163603130656475864162239004344663459120398951306959672239055329877644796995008368282924624780849432051543118959312685532106237568240835778731486989439626252834661294225426875963944816709371554839452465119058016363040631618359944564550348310851045841670935254841385590882490443247265126417117450357
dp = 13530055667815347122266109008252377134325151556131892235929064596659462917644020624855537451062167377041847601387880412738836767351591511886432133011921729
c = 23428056833770750219439218340180501853506449797628734848807388355447212714387039203998085387476974936419607861041793755542930286287098871510394661091846780839592290953853536571372997807697657464569729651718518301857979495046280018444198435962234642736892075369840282923945267377104440625478468507147243879631

m1 = 3
c1 = pow(m1, e, n)
mp = pow(c1, dp, n)
p = gcd(m1 - mp, n)
q = n / p
d = modinv(e, (p-1) * (q - 1))
m = pow(c, d, n)
print hex(m)[2:-1].decode("hex")```

The code implements the method described in the paper. Run it, get flag, ???, profit.

Flag: `flag{wow_leaking_dp_breaks_rsa?_47413771836}`