Tags: crypto
Rating:
# Security Through Obscurity - 150 Points
I've never seen such a cryptosystem before! It looks like a public key cryptosystem, though... Could you help me crack it?
[encrypt.sage](https://raw.githubusercontent.com/EasyCTF/easyctf-2017-problems/master/security-through-obscurity/encrypt.sage)
[publickey and ciphertext.txt](https://raw.githubusercontent.com/EasyCTF/easyctf-2017-problems/master/security-through-obscurity/publickey_and_ciphertext.txt)
### Solution
###### Writeup by VoidMercy from phsst
We were given an encryption program, and a publickey and ciphertext shown below:
```python
p = 196732205348849427366498732223276547339
secret = REDACTED
def calc_root(num, mod, n):
f = GF(mod)
temp = f(num)
return temp.nth_root(n)
def gen_v_list(primelist, p, secret):
a = []
for prime in primelist:
a.append(calc_root(prime, p, secret))
return a
def decodeInt(i, primelist):
pl = sorted(primelist)[::-1]
out = ''
for j in pl:
if i%j == 0:
out += '1'
else:
out += '0'
return out
def bin2asc(b):
return hex(int(b,2)).replace('0x','').decode('hex')
primelist = [2,3,5,7,11,13,17,19,23,29,31,37,43,47,53,59]
message = REDACTED
chunks = []
for i in range(0,len(message),2):
chunks += [message[i:i+2]]
vlist = gen_v_list(primelist,p,secret)
print(vlist)
for chunk in chunks:
binarized = bin(int(chunk.encode('hex'),16)).replace('0b','').zfill(16)[::-1] #lsb first
enc = 1
for bit in range(len(binarized)):
enc *= vlist[bit]**int(binarized[bit])
enc = enc%p
print(enc)
```
```
p = 196732205348849427366498732223276547339
vlist = [186290890175539004453897585557650819247, 75402298316736094226532182518108134406, 125495142022496378270547998225256386407, 97774267687164931514953833940936099082, 101991197227908059637463567354647370660, 153833851791059142883915934225837717549, 57404874013093467650483424580890463792, 21385179362692238453302681296928238570, 73119997627509808412069264512026243174, 187307466063352771786747395191866088255, 99696708971915885525739992181010504930, 35400960589917132410614021764179554582, 165004028169785856134522269878963539096, 23921651712221317415895203722083962980, 101282552285744196401422074083408273639, 36527324251768098978171373433957274016]
ciphertext = [10804437392992369932709952388461430442, 176193785024128365464527424154073333243, 149270645998191619421663334736314262928, 84083279828403258970202482839973583723, 105542809657403162156368566034837560781, 170535468317794277192003839288646533914, 1709561989051017137832962458645802494, 30208132812353075834728747743616689590, 179552149608863037880916374596103803214, 146319871444551859531557724256502213689, 94266034977624098660397183255753485858, 59624105602644297614582310044425417646, 150207980679551836987813576795479579005, 47189940152625174480564945084004798024, 60923399917552243674613186036841652885, 56060552313063913798237738953734149992, 153365453785043472981157196787373992079, 97439800863356756323659264743487719966, 105572255903480949865247928773026019148, 47189940152625174480564945084004798024, 32547907449246015626932936731350157592, 97471053149217334376536988401195572824, 156999991149661497460742185971412527182, 97705058765750947378422286408948780428, 56123764944636237849915747435965967337, 180380146745295930385428990214293723238, 178014626944341285289827069179285260436, 99504741454750536629756505680249931430]
```
Looking at the information provided, we can surmise that we have to find the value for message to make the program output the given ciphertext. "secret" looks like a red herring because it plays no part in the message encryption, as vlist was given to us, and secret was only used to generate vlist. As such, we focus on the latter half of the program.
We can see that each "chunk" is 2 characters of the message, and it iterates through each chunk of 2. Then, this chunk is converted into binary, and padded with zeroes. Then, each bit of this chunk is used to determine the number in vlist to be multiplied into the ciphertext. For example, if the first bit is a 1, then the first element in vlist will be multiplied to the ciphertext. Similarly, if the nth bit is a 1, then the nth element in vlist will be multiplied. Then, enc is modded by p.
Because this program encodes chunks of two, there are only 0xFFFF different possible characters (Two bytes for each character). As such, we can brute force which characters would encrypt to the letter in the ciphertext. Here is my script to do so:
```python
p = 196732205348849427366498732223276547339
ciphertext = [10804437392992369932709952388461430442, 176193785024128365464527424154073333243, 149270645998191619421663334736314262928, 84083279828403258970202482839973583723, 105542809657403162156368566034837560781, 170535468317794277192003839288646533914, 1709561989051017137832962458645802494, 30208132812353075834728747743616689590, 179552149608863037880916374596103803214, 146319871444551859531557724256502213689, 94266034977624098660397183255753485858, 59624105602644297614582310044425417646, 150207980679551836987813576795479579005, 47189940152625174480564945084004798024, 60923399917552243674613186036841652885, 56060552313063913798237738953734149992, 153365453785043472981157196787373992079, 97439800863356756323659264743487719966, 105572255903480949865247928773026019148, 47189940152625174480564945084004798024, 32547907449246015626932936731350157592, 97471053149217334376536988401195572824, 156999991149661497460742185971412527182, 97705058765750947378422286408948780428, 56123764944636237849915747435965967337, 180380146745295930385428990214293723238, 178014626944341285289827069179285260436, 99504741454750536629756505680249931430]
vlist = [186290890175539004453897585557650819247, 75402298316736094226532182518108134406, 125495142022496378270547998225256386407, 97774267687164931514953833940936099082, 101991197227908059637463567354647370660, 153833851791059142883915934225837717549, 57404874013093467650483424580890463792, 21385179362692238453302681296928238570, 73119997627509808412069264512026243174, 187307466063352771786747395191866088255, 99696708971915885525739992181010504930, 35400960589917132410614021764179554582, 165004028169785856134522269878963539096, 23921651712221317415895203722083962980, 101282552285744196401422074083408273639, 36527324251768098978171373433957274016]
print (vlist)
ans = ("1 " * 40).strip().split(" ")
for i in range(65536):
cur = bin(i).replace("0b", "")[::-1]
enc = 1
for bit in range(len(cur)):
enc *= vlist[bit]**int(cur[bit])
enc = int(enc % p)
if (enc in ciphertext):
#print (cur[::-1].zfill(16))
temp = cur[::-1].zfill(16)
index = ciphertext.index(enc)
ans[index] = chr(int(temp[:-8], 2)) + chr(int(temp[8:], 2))
print ("".join(ans))
```
The result is:
```
flag{i_actu4lly_d0nt_know_th3_name_of_115_crypt0sy5tem}111111111111
```
When we entered this, it didn't work, but we can see that _115_ would make more sense as _th15_. So we changed this, submitted, and it worked. (Don't know why there was a problem... and also this flag doesn't start with easyctf!!!).
## Flag
>flag{i_actu4lly_d0nt_know_th3_name_of_th15_crypt0sy5tem}
