# Little Nightmares
## Overview
The beginning of keygen() looks like RSA key creation.
But following ``N = p*q`` is taking 3 random numbers smaller then m, and then some math stuff I don't recognize from any cipher.
Anyhow, with the variable names public and private, and the fact that the key has 2 parts ``public = [N, g1, g2], private = [p, q]`` this almost certainly is a public key encryption.
So I went off to do some research, basically just having a look at all these [encryption protocols](https://en.wikipedia.org/wiki/Public-key_cryptography#Examples).

## Public Key Encryptions
### -> [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem))
RSA requires two exponents that are their multiplicative inverse, meaning ``e*d % N = 1``.
But that's nowhere found in the code, and the other variables would not make sense in RSA.

### -> [Rabin Cipher](https://en.wikipedia.org/wiki/Rabin_cryptosystem)
My next guess was the Rabin cipher. I remember having solved a (chal)[../imaginary/Round5/batmans-cipherkick] with it.
Although some of the variable names match (r1, r2, p, q), the rest would not make sense (especially the encryption and decryption).

### -> [Diffie Hellman](https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange) / [ElGamal](https://en.wikipedia.org/wiki/ElGamal_encryption)
Both of those require the same math, so if one fits, the other should too.
Again, the variable names and count seem off, and they only use one ciphertext.

### -> [Eliptic Curve Cryptography](https://en.wikipedia.org/wiki/Elliptic-curve_cryptography)
Again, the script would just not make sense with ECC, there are no signs of a curve and their parameters.
If this was used, there would be way more code or the use of an external library.

### -> [Paillier Cryptosystem](https://en.wikipedia.org/wiki/Paillier_cryptosystem)
Too be honest, I don't fully get how this works, but it looks similar to RSA with it's multiplicative inverse.
And we ruled out RSA, so this is out too.

### -> [YAK](https://en.wikipedia.org/wiki/YAK_(cryptography))
Again, I don't fully get how this works, but this looks like Diffie Hellman.
And because the variables are still off, this isn't it either.

### -> [Cramer-Shoup Cryptosystem](https://en.wikipedia.org/wiki/Cramer%E2%80%93Shoup_cryptosystem)
For the last time, I don't fully get how this works, but it does not seem to be it.

## Further Research
As it seems, this might be some own crypto system.
So for me to solve this, because I don't fully get how this works, I still have to get lucky and get the weakness of this cipher via OSINT.

### Dartmouth Homework Task
After some trial and error, with this google query "public key N g1 g2" I found an interesting [pdf](https://math.dartmouth.edu/~m75s18/hw6.pdf), some homework from Dartmouth Uni.
As it seems, Cryptohack copied Dartmouth Uni's algorithm or vice-versa.
Anyhow, on the pdf is only "b) Explain why this cryptosystem is not secure." and the note "Problem 3.10 from the book."
Further OSINT revealed the [course](https://math.dartmouth.edu/~m75s18/) and the [book](https://www.amazon.com/Introduction-Mathematical-Cryptography-Undergraduate-Mathematics/dp/1493917102/) that was mentioned.
Now, I don't feel like paying some 70$ without event guaranteeing solving the challenge.
So I'll have to keep my OSINT cap on and find the solutions for free and then eventually solving it.
Some times later with the following google query: "an introduction to mathematical cryptography 3.10 solutions" if found some [solutions](https://usermanual.wiki/Pdf/SolutionsManual.1797252236/help).

## Solving
They describe the primes can be recovered with ``gcd(g1 − 1, N ) = p``, because of Fermat's Little Theorem (I still don't fully get why).
Anyhow, with maximum cheese I recovered a prime, got the 2nd prime with ``q = N // p`` and finally got the flag with ``long_to_bytes(decrypt((c1,c2), (p,q)))``.
Thank you Dartmouth Uni for your kind help. :P