Rating: 5.0
>"RSA is just math". And now, there is a cryptosystem that simpler than RSA, but, "Simple is the Best!"
[simple.py](./simple.py) [pubkey.txt](./pubkey.txt) [enc.txt](./enc.txt)
Looking at [simple.py](./simple.py):
```
from Crypto.Util.number import *
import random
from flag import FLAG
def generate(nbits):
p = getPrime(nbits)
q = getPrime(nbits)
n = p * q * p
g = random.randint(1, n)
h = pow(g, n, n)
return (n, g, h)
def encrypt(m, n, g, h):
r = random.randint(1, n)
c = pow(pow(g, m, n) * pow(h, r, n), 1, n)
return c
m = [ord(char) for char in FLAG]
n, g, h = generate(90)
open("pubkey.txt", "w").write("{0}:{1}:{2}".format(n, g, h))
c = [encrypt(mi, n, g, h) for mi in m]
open("enc.txt", "w").write(str(c))
```
We see that our `n` is generated as `p^2*q`, where `p` and `q` are 90 bit primes. 90 bits is a little too difficult to use regular attacks on, so we have to look at another avenue. Our `c` is calculated as follows:
`c = (g^m mod n) * (h^r mod n) mod n`
We can just rewrite this as
`c = (g^m) * (h^r) mod n`
We are also given the `n`, `g`, and `h` values as:
```
n = 1235280093599323856390922798440377476467763531842392869674688408727824382702235317
g = 1110549711091392805024587195974719739929628997819528005374351081843256209971586072
h = 610466084395822279908554174354632326166097007218620288020807622478449585661028278
```
We can use [FactorDB](http://factordb.com/index.php?query=1235280093599323856390922798440377476467763531842392869674688408727824382702235317) to factor our `n` value and get the `p` and `q` values. So `p` and `q` are as follows:
```
p = 1057817919251064684989791981
q = 1103935256393984899021164397
```
Now we are given in the question that this custom cryptosystem is simpler than RSA, but it does look similar to it. Specifically in RSA, it uses a public exponent (e) and a private exponent (d), and encryption is defined as `c = m^e mod n` and decryption is defined as `m = c^d mod n`, where `m` is our message and `c` is our ciphertext and `n` is our modulus. Normally you're only given `n` and `e`, but if you know the factors of `n`, then you figure out the value of `d`. This is because `e` and `d` are normally chosen so that `ed = 1 mod (totient(n))`.
Now the totient of a number `n` is defined as the number of positive integers less than or equal to `n` that are co-prime to `n`. It was further proven by Euler that if `p` is prime and `k` is greater than or equal to 1, then `totient(p^k) = p^k(1 - 1/p)` and that if `n = p * q`, where `p` and `q` are primes, then `totient(n) = totient(p) * totient(q)`. Now with our example, we know that `n = p^2 * q` and we know the values of `n`, `p`, and `q`. So the `totient(n) = totient(p^2) * totient(q) = (p^2(1 - 1/p)) * (q(1 - 1/q)) = p * (p - 1) * (q - 1)`.
So what do we do with the `totient(n)`? Well according to [Euler's Theorem](https://en.wikipedia.org/wiki/Euler%27s_theorem), `a^totient(n) = 1 mod n`, given that `a` and `n` are co-prime. However, we see that `g`, `h` and all of the `c` values are all co-prime to `n`, so if we raise both sides of our `c = (g^m) * (h^r) mod n` equation to the power of `totient(n)`, we will just get `1 = 1 * 1 mod n`, which doesn't help. However, [further research](http://home.scarlet.be/math/congr.htm#The-smallest-solutio) reveals that the smallest solution for `x` to `a^x = 1 mod n` may not be `totient(n)`.
We want to find a smaller solution, so let's assume that `x` is less than or equal to our `totient(n)` Starting with `a^totient(n) = 1 mod n`, we express `totient(n) = q * x + r`, so `q` is the quotient and `r` is the remainder (r < x). So `1 = a^(totient(n)) mod n = a^(q * x + r) mod n = 1 * a^r mod n = a^r mod n`. We know that r < x, so the only solution is `r = 0`, so that means `totient(n) = q * x`, so that means the smallest solution to `a^x = 1 mod n` is a divisor of `totient(n)`. Note that this includes `totient(n)`, and this value is related to the [Carmichael function](https://en.wikipedia.org/wiki/Carmichael_function).
So we can test the divisors of our `totient(n) = p * (p - 1) * (q - 1)` and see which ones gives us useful information. The plan is to get a divisor so that `h^r` raised to the power of that divisor is 1 and we can remove that from the our equation but the other two values aren't 1. We see that using `(p - 1) * (q - 1)` accomplishes this.
Basically `h^r` raised to the power of `(p - 1) * (q - 1)` or `h^(r * (p - 1) * (q - 1))` equals 1 no matter what value `r` is because `h^((p - 1) * (q - 1))` equals 1, and 1 to the power of anything is still 1. If we raise our `c` and `g` to the power of `(p - 1) * (q - 1)` however, we don't get 1.
From our original equation:
`c = (g^m) * (h^r) mod n`
We raise both sides to the power of `(p - 1) * (q - 1)`
`c^((p - 1) * (q - 1)) = g^(m * (p - 1) * (q - 1)) * h^(r * (p - 1) * (q - 1)) mod n`
As we stated above `h^(r * (p - 1) * (q - 1)) = 1 mod n` so our equation is now
`c^((p - 1) * (q - 1)) = g^(m * (p - 1) * (q - 1)) mod n`
Now we can just brute force through the possible values of `m` (since `m` is a character of our flag, it's in between 0 and 255 inclusive) and check when `c^((p - 1) * (q - 1)) == g^(m * (p - 1) * (q - 1)) mod n`. The following script accomplishes this:
```
n = 1235280093599323856390922798440377476467763531842392869674688408727824382702235317
g = 1110549711091392805024587195974719739929628997819528005374351081843256209971586072
h = 610466084395822279908554174354632326166097007218620288020807622478449585661028278
p = 1057817919251064684989791981
q = 1103935256393984899021164397
phi = p*(p-1)*(q-1);
tphi = (p-1)*(q-1);
cs = [1042684026433440609442082085056733059350277230855631475910449335289565957026925888L, 337451979363258259789969117391527857381178461709773977486124377788140579446959643L, 955044246855117318302069848746627916980637349888954523552188603828273408620783185L, 565084528151941455613387670829541401837686258558304725363697970401158298304784226L, 1217257199494998716855441753878986048959547533911751395319106679987808998530722005L, 500431401136979664818320806505265313829298163109190333815615071157569573408761776L, 918364738570517634370611128928418073524271175997413722821007998543195365584145047L, 1231818404429995719463458343454764290314747233553619629902141039984717307144020885L, 578663363706556074852662555903558050626510818844939214634690712022753850484044077L, 170573141141793020278685561667014942396340687197982787584671361315770701412232820L, 525046404028002961161648698133126471909762913783905233407759137018767422695415644L, 548918541683229869313458652944252600295112072416629330975730507209045241266103104L, 1097888538672145356012505481951969976746432194049237781078685846091302406138295450L, 467055824810727038529002950991149449402485370247343520114443047715384113252663243L, 379325228947504950566222318955652420189554769276755237788381017120582088704791796L, 808135517143354496893964869359259307455178022544381266003759602027195395780858971L, 232206696206622845104449934990777760916638497611027428059484100417419468488368534L, 611231502156630905749534239244947175924425232566020566839692916151929122262556160L, 266317680779170923895607136980535234290396471711461778811550899033797067803838490L, 458442169696983024890517742499158555610082173984048562536247204694360339657234325L, 173156860778775111311074302992389403207838028758953619505920477407616091727957249L, 327701451317276442403593523928518039719286029867533592333080575014882858204660392L, 1061889651976594791626195662010361995350291121541576461530446716234559629390059206L, 501107468516571472868902583880130438298825499145194993732906902954639206415408661L, 793462123972295663612808938124574874398657924694272939619742740367249265250881187L, 419580729971386599858472445685002497860174205402938481254320715563201540618526181L, 1095670842511297949652166375966107611580541850315423104099581710112461928501516645L, 1207404101728741308518114885496775915613418535791624006547396431596035842097919854L, 63257756791404477719948396035346460877053804738003821615924989712602434088623116L, 709743404772556668186521811311910146690879578711491970215935941312652194503904278L, 472145667401895260338686064243470672627707713552548730414485106260542589178719305L, 671679182553553455773258809387401495029229971280677124071355178172582087439182089L, 795683594959663064302728712706823881033923895027131034114737749301583410828859935L, 788511687111620345727088836755516496428115065618134997006646145097528302404655271L, 493455498376449391174132961453557751413575238351804592824587799692504725075730030L, 1071336432168555760392522471606603558083343440707490972056560901765084761996537479L, 76414279730707452882500835328589558586805800097281864786868179845530554318636818L, 1026789233929477564953495880177610952920067780854127113113934470636602509593246257L, 1220456099417710433363957577456670914480321272794999438920511570648408214807875401L, 831001855794529333359541390744984608592774868529241373516540331083225538929223854L, 406700540669900202178972508513521627652422698239818055618399192500676530118703988L, 535793870780869641948563592689023912632863260901941937211057060307409713921739965L, 908165522898293977370960880692560887898587015153655232763363739940417879927826149L, 916463042698051909403902218425035797085521743060997736870228165259059940402603712L, 1124064575055728289901493663250187815236366261544380516480084011806758657972869579L, 302544873761485689612490183241038411927316560916804219683347601892406383914571353L, 326809752614724517585542018284901481393260541798889339649409227233748588383860516L, 828292723696438834080952146252731883891295126479141546958923438287859173086057154L, 835877660712133206131980242990809426528248997858916518574414436451562226433887025L, 145587585798997332370407645289128453608803108424500991984349925153212212859373727L, 463948250139563696175107900326108271430940645044009515704115508942300583165355378L, 944242052057563352409261236875599145504153562928055236566287627433096232314943101L, 579193856270128178962709647899702648998261560149392089962175236519890756116448359L, 1167987057311285845643231967769257342900085143163437221731184706561190379437889873L]
flag = '';
for c in cs:
temp = pow(c, tphi, n);
for f in xrange(256):
if temp == pow(g, f*tphi, n):
flag += chr(f);
print flag;
```
Running the script we get our flag: `MeePwnCTF{well_is_fact0rizati0n_0nly_w4y_to_s0lve_it?}`
