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?}