Title: CTF's Crpto Exercise Three

DES weak encryption easy_BlockCipher

Download the attachment and get 2 files: https://adworld.xctf.org.cn/media/task/attachments/5b8bcb28546b4423b481b13149abc99f.zip Analyze the question, and the code for encryption is given in the question.

des-ofb.py:

from Crypto.Cipher import DES

f=open('key.txt', 'r')

key_hex=f.readline()[:-1] # discard newline

f.close()

KEY=key_hex.decode('hex')

IV='13245678'

a=DES.new(KEY, DES.MODE_OFB, IV)

f=open('plaintext', 'r')

plaintext=f.read()

f.close()

ciphertext=a.encrypt(plaintext)

f=open('ciphertext', 'w')

f.write(ciphertext)

f.close() shows that the DES algorithm is used during encryption, and the plaintext is encrypted in OFB mode.

Therefore, in the case of known IV=‘12345678’, you only need to know the Key to crack the ciphertext.

According to known information, there are only IVs and unknown keys, so it is thought that there are weak keys in DES encryption. In DES calculation, the 56bit key will eventually be processed as 16 round keys, and each round key is used for one round of 16 rounds of calculations. The DES weak key will make these 16 round keys completely consistent, so it is called a weak key.

Four of the weak keys are:

0x00000000000000000

0xFFFFFFFFFFFFFFFFFFFFFFFFF

0xE1E1E1E1F0F0F0F0

0x1E1E1E1E0F0F0F0F uses four sets of keys to try to crack the ciphertext.

from Crypto.Cipher import DES

f=open('ciphertext', 'r')

ciphertext=f.read()

f.close()

IV='13245678'

KEY=b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

a=DES.new(KEY, DES.MODE_OFB, IV)

plaintext=a.decrypt(ciphertext)

print plaintext

KEY=b'\x1E\x1E\x1E\x1E\x0F\x0F\x0F\x0F\x0F'

a=DES.new(KEY, DES.MODE_OFB, IV)

plaintext=a.decrypt(ciphertext)

print plaintext

KEY='\xE1\xE1\xE1\xE1\xF0\xF0\xF0\xF0\xF0'

a=DES.new(KEY, DES.MODE_OFB, IV)

plaintext=a.decrypt(ciphertext)

print plaintext

KEY='\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF'

a=DES.new(KEY, DES.MODE_OFB, IV)

plaintext=a.decrypt(ciphertext)

print plaintext from the results obtained is a poem by Shakespeare.

or script: #coding:utf-8

from Crypto.Cipher import DES

import libnum

ct=open('ciphertext','rb').read()

KEY=libnum.n2s(0xe0e0e0e0f1f1f1f1)

IV='13245678'

a=DES.new(KEY,DES.MODE_OFB,IV)

print a.decrypt(ct) Finally got flag:flag{_poor_single_dog_has_found_an_echo_from_it}

RSA algorithm special-rsa

Question description: When learning the RSA algorithm, I found an algorithm with the same security as RSA. Encrypting msg.txt gets msg.enc. $ python special_rsa.py enc msg.txt msg.enc Can you recover flag.txt from flag.enc? Download the attachment, which contains 4 files, as follows: https://adworld.xctf.org.cn/media/task/attachments/7a407f44a073442c91fd395b20594f01.zipflag.enc

special_rsa.py

msg.enc

msg.txt

The idea of the question is to use the hidden key to decrypt the flag.enc file. After reading the special_rsa.py file encryption and decryption process, I made a simple formula to find the hidden key.

The pseudo-code is as follows:

flag.sage:

N=2392741101402069577293491676495366164131014848097705664525509819249174035652524067590628570051635757892994011455370097616796996436414961522656868922422802 84616866172935341157887799555978779650445704934575674208747413571865964257536674552668704021545524398996644464136327167476448548975519407775125220449071328 6490564421265538722330241089687108075176822409176093420991798421358551351059761970879768870587680546488010579782938032655939972304809217549220389446875271 8008631464599810632513162129223356467602508095356584405555329096159917957389834381018137378015593755767450675441331998683799788355179363368220408879117131L

c1=1454899738089726523977888482538130110996551898966180809068895223238109172676146495957294338302442802827071762995389459289085912881883932849900295082849152 1254480795364789013196240119403187073307558598496713832435709741997056117831860370227155633169019665564392649528306986826960829410120348913586592199732730 9332598804692297241498873800056273217528434895649843587080133005246405454377037714241681082130455675685950934213662248186095013187836804977633536181101840 78118456368631056649526433730408976988014678391205055298782061128568056163894010397245301425676232126267874656710256838457728944370612289985071385621160886

c2=127939427951100383197245318755686935074693271760859541640347287275111648333510175515351403025615287836466407905656538533190119654101539360975162497155401 6671160730478932343949538202167508319292084519621768851878526657022981883304260886841513342396524869530063372782511380879783246034751883691295368172069170 9679755613642775140633206919309002580172938717542522097273017192076923217982292767321985217116020802449502958895754233833080997862981844776683028429522156 65734671829249323604032320696267130330613134368640401070775927197554082071807605399448960911234829590548855031180158567578928333030631307816223152118126597

m1=8246074182642091125578311828374843698994233243811347691229334829218700728624047916518503687366611595562099039411430662968666847086659721231623198995017758 4247960918102598846533325761361281449587513278447469912646670073595181813635229344306766552368804895500938525248013046123223735422962819621967953044997110 0680121178300585729736293033897887245193486043559754564221921355168597320820987362390962927832118148501096446065229869005874709029831236523067172379085099 8541956664376820820570709272500330966205578898690396706695024001970727864091436518202414166919020415892764617055978488996164642229582717493375419993187360

m2=1557505145385852175310846206372375098638609306776394831661215794619083552733264120183706295101222781556841830916647308058835456242606669492436488691640815057608266779727400066172627987197137743836282940252968282547129986181482946 3510659258586020732228351258291527965822977048954720558973840956731377322516168809373640494227129998871167089589689796024458501705704779109152762373660542684880052489213039920383757930855300338529058000330103359636123251274293258

r1=12900676191620430360427117641859547516838813596331616166760756921115466932766990479475373384324634210232168544745677888398849094363202992662466063289599443

r2=7718975159402389617924543100113967512280131630286624078102368166185443466262861344357647019797762407935675150925250503475336639811981984126529557679881059

_, a, b=xgcd(r1, r2)

k=pow((c1/m1 % N), a, N) * pow((c2/m2 % N), b, N)

print (k)

get key:

1759717765420958225905954052742586682712713663601405787766125822769665670820803729808113101462173995859382147129287615595256148661138215514678422215884326 76885027725038849513527080849158072296957428701767142294778752742980766436072183367444762212399986777124093501619273513421803177347181063254421492621011961

Get the key, decrypt flag.enc, get the answer:

port msgpackdef 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) assert g==1 return x % mdef pad_even(x): return ('', '0')[len(x)%2] + xdef decrypt(c, k): out='' for r_s, c_s in msgpack.unpackb(c): r=int(r_s.encode('hex'), 16) c=int(c_s.encode('hex'), 16) k_inv=modinv(k, N) out +=pad_even(format(pow(k_inv, r, N) * c % N, 'x')).decode('hex') return outN=2392741101402069577293491676495366164131014848097705664525509819249174035652524067590628570051635757892994011455370097616796996436414961522656868922422802 84616866172935341157887799555978779650445704934575674208747413571865964257536674552668704021545524398996644464136327167476448548975519407775125220449071328 6490564421265538722330241089687108075176822409176093420991798421358551351059761970879768870587680546488010579782938032655939972304809217549220389446875271 8008631464599810632513162129223356467602508095356584405555329096159917957389834381018137378015593755767450675441331998683799788355179363368220408879117131k=1759717765420958225905954052742586682712713663601405787766125822769665670820803729808113101462173995859382147129287615595256148661138215514678422215884326768 85027725038849513527080849158072296957428701767142294778752742980766436072183367444762212399986777124093501619273513421803177347181063254421492621011961print decrypt(open('flag.enc').read(), k)

Finally got flag:

Flag: BCTF{q00000000000b333333333-ju57-w0n-pwn20wn!!!} Title description: It seems easy, right?Tip: openssl rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc

The title gives a flag.enc and a public.pem, and the attachment download address:

https://adworld.xctf.org.cn/media/task/attachments/9244cc370caa43f491636f8c4670fe7d.zip

Installing openssl can read n and e. Because n is not big, you can decompose it on yafu or factordb.com to get n=p * q * r

According to flag.enc, the ciphertext m can be obtained

According to the Chinese residual theorem, we require the remainder of m under p, q, r, and may as be set to pmod, qmod, rmod,

Then, based on the remaining mode three times, i.e. proot ^ 3 ≡ pmod ( mod p), find: proot, same is true for qroot, rroot

Using web tools, you can directly calculate:

http://www.wolframalpha.com/input/?i=x%5E3+%3D+19342563376936634263836075415482+(mod+27038194053540661979045656526063)

We get a ciphertext from the openssl command line that seems to be encrypted via RSA. We also have access to the public key, so we do the following by restoring the parameters, just like using a standard RSA password:

e=3

n=23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067

Using YAFU, we divide the modulus into:

p=26440615366395242196516853423447

q=27038194053540661979045656526063

r=32581479300404876772405716877547

We get three prime numbers. This is still good, it may just be multi-quality RSA. This is not surprising at all. Generally speaking, it is very simple (p-1)(q-1)(r-1), and the rest of the calculations are carried out as usual. But it does not exist because we find that the modular multiplication inverse does not exist. The reason is obvious: gcd(e, to client)=3, should be 1. This is not the first time we have encountered a similar situation (such as https://github.com/p4-team/ctf/tree/master/2015-10-18-hitcon/crypto 314-u rsabin-35; eng version), so we have some ideas on how to deal with this.

Before applying RSA decoding, we need to remove these 3. This means that encryption is:

ciphertext=plaintext^e mod n=(plaintext^e')^3 mod n

So if we can form the modulus cube root (mod n) on both sides of the equation, we can use e'=e/3 for RSA decoding. Since e=3, e'=e/3=1, so it's not easy here, which means our encryption is simple:

ciphertext=plaintext^3 mod n

Therefore, the entire decryption process requires the mod cube root (mod n) in the ciphertext.

Some readings about mould roots lead us to the conclusion that this is possible, but only in limited areas. So it can't do with n, it's a composite number, we know it is because it's pqr.

This question reminds us of the Chinese reminder theorem (https://en.wikipedia.org/wiki/Chinese_remainder_theorem). After thinking for a while, we came up with the idea that if we can calculate the three-time mold roots of 3 primes from the ciphertext (mod prime), we can calculate the merge roots. We can achieve this using the Gaussian algorithm (http://www.di-mgt.com.au/crt.html#gaussalg).

So we continue to calculate:

pt^3 mod p=ciperhtext mod p=20827907988103030784078915883129

pt^3 mod q=ciperhtext mod q=19342563376936634263836075415482

pt^3 mod r=ciperhtext mod r=10525283947807760227880406671000

Then we took a while to solve this equation of pt, and finally we found that wolframalpha implements this function, for example:

http://www.wolframalpha.com/input/?i=x^3+%3D+2