---
title: CRYPTO CTF
tags: Crypto
lang: zh_tw
---

# CRYPTO CTF

[toc]

## CRYPTO
### 100-mama

nc 140.110.112.30 5001

>This task is inspired by one of my favorite crypto challenge, primitive from starCTF 2018, and its writeup from p4. The original challenge use ARX (add, rotate and xor) to construct arbitary permutation. I suggest thinking of this challenge before continuing reading (It's very interesting). I also provide a formulated solution of primitive in appendix at the bottom.
>
> This task, mama, use multiplication and addition instead of ARX, but the solution are very similar. I also choose a large p (128 bits), so you need to find a way to construct it rather than bruteforce.

---

### 300-xorlnarmoni'akda

nc 140.110.112.30 5003

> The key vulnerability is small subgroup attack under multiplicative DHKE. By sending a element in that small group, there won't be too much possible shared secrets.
>
> This is a simple modern crytographic challenge, which may deserve 100 points in normal CTF. However, this challenge requires you to have some basic knowledge of number theory, otherwise you won't even notice the existence of subgroup. I also put some effort to make it more interesting to experienced crypto solvers, such as introducing a guest account, PBKDF2, using flag as password, and the most confusing one: obfuscation by a obsecure language.

---

### crypto-primitive

nc 140.110.112.30 5004

> The ADD ROTATE XOR are three basic operations for many modern block ciphers. And it's possible to build any sbox using ADD and ROTATE only. For example, operations (0,2),(1,7),(0,255),(1,1) gives a construction for transposition of adjacent elements 254 and 255. However, for arbitrary pair a,b the direct construction with ADD ROTATE can take too much steps while we have a limit of 2000. But with XOR operation, we can change any pair a,b to 0,1 with steps in proportion to element's bit number. Since we can swap any pair now, it would be trivial to build a proper cipher.

## Level 1
### **Caesar cipher**

IylhrHSSJAM{QRJrqYZYEYotoaHIemgw}

---

### **YANG_RSA-1**
> 提示1 : n很小可以使用 http://factordb.com/ 先分解出p和q質數
提示2 : 分解出p和q質數後算出d，用d去解c

n = 83092583783534841000145280642003842283533340442637642451258941907393275732996256523893438356692786223410880194199043046345864683398238392329295750150314289824255749149834103

e = 11

c = 32392151763267291269610586564983347951891395196084251182633225594245167922176424232164117237142038355860036871811244158149537196288428230971760474130300660929743492107190512

---

### **YANG_RSA-2**
> RSA的加密過程是m的e次方mod n得到c。
在傳統的過程中，會習慣將e設為3或者65537，因為以平方再乘法演算法中可以進行加速。
早期大多會以e =3為主，而m又不可以大於n，如果m不夠大且e = 3，則有可能m的e次方小於n，造成 c = m的e次方
>
> 提示1: 不用分解n太大了
提示2: 因為n太大，故直接把c開e次方根

n = 1005098784594165848821832590501628403524802902674053382968470498538675288024873128424879364961488454145355936225677709124632789481770148984368708158164916266844271786072406765898627538801884748356080826075494258116818573097428235536790636847100997446916017821607591551722483794674940379793999230206353715117589898489861301662334780242666620337676110221421426102941068711974618344098371538140671153829377393837740293830337243493085160451872753422509384072905634851957789103689582476286664749588114456827960476870164048784404280351460249562996906271414272625881748849175309114734205368513000888013065441040602267654552015590863773059574256085653649422840863428324602357578340644446996674941825103598620438972286389472676382307637357209115141975325946791432841852827828407465818721747161090664009799105129953728589693126992849713556841586265400095017954688319716059398240941350468461830314384384626840855999556176928576367255322330539451380078690665639135509274932616776447492100759094249811584415361859939091438557866035439570864472528889723274777281738473905899882030941410513275852891694991922437995200537246398155615904052214367857177598437501143127042446835618109714924845047124233631838729882640996639575165133299706184551662489093

e = 7

c = 44163895521220531459057055795752057167876718238617963549906371036055586914199267109947281359325715489398261335563468559859879340774499726524035061903919328383390193234339356811666801858858748990899697833645511123626735258871404048116302274347058468791179874933001105300534600581977271895856972533976629641765182868484553104584590829347999386472615066779248550781718812068424236647225425670871554757459074630360567280382876137651283102473254886990887517217176132596555364994651622062720390486911698802074418697530462711619997107804919499320409084297665919116751543056038865957808455949742740596859550586982302492545205898434968509344729243293414190715139959127090472661918871372070659935437431160846169010492251366727698703670348564864343164944932175842131148853297549424891479394079434940030257530096990169847176293150870765433888895069248560702669885642923421945661068042034911026426121363007026093515922333722778955975053692081279596854554640425470049534192255739670036469

---

### **YANG_RSA-3**
> 孿生質數(Twin prime)指假設 p 是質數且 p + 2 也是質數
如 (3,5), (17,19), (41,43) …
>
> 在RSA中，如果有兩把公鑰其符合 n1 = p q n2 = (p+2) (q+2)
則可以在不用分解 n 的情況下得到 phi 來進行解密。
> 提示1 : 可以參考此篇簡報第8頁
https://www.slideshare.net/ssuseraba268/rsa-in-ctf
> 提示2 : 也可以參考其它CTF write up
https://ctftime.org/task/2731

from Crypto.Util import number

def getTwin(n):
	while True:
		p = number.getPrime(n)
		if number.isPrime(p+2):
			return p

p = getTwin(1650)
q = getTwin(2000)
n1 = p * q
n2 = (p+2) * (q+2)
e = 10000001
m = libnum.s2n(open('flag').read().strip())
c = pow(pow(m,e,n1),e,n2)

with open('output.txt','w') as f:
	f.write('c = %d \n\n' % c)
	f.write('e = %d \n\n' % e)
	f.write('n1 = %d \n\n' % n1)
	f.write('n2 = %d \n\n' % n2)

c = 139042738526108915518382315590614161559545672874231013930043771888153330995636895021496690157019719891495421789891311751114070162820109898550748729125606711558619118645191771802867431417997808791808947663873157450381886576198018116644175503419727838166069179286320364053606871929319609609717883881827703531071294250903725115590903885439257993122448450155592341119519506480784700882637629148100289455951870378287065580019819787172666799064867472787388018501312484677758639630205985303521919625967928777576894714176370710514866851261857421113481579194403231201302648732458813285636116381750742800141620920665296851274731594398742733371863332481364651903565612256089078337832051794479664232703579382433662773172010772985745670472577141377427032667489413571147659184721008370862939384402765999758594739567633919697832750413509665699046792692953501205991502771826582951017086701333243949551066796272454956773817169423364362577405931516463850167131352119912514527378117187253789191465090914208628886222374130328836743075062815304664169005843065539134914179702827261596407513474449624318873499341773097243

e = 10000001

n1 = 3627444771006641937670374103598493492277170277116493920932885955435916968318288577415856168749785331840818803112714250474056975340846972000039130600885450836486139285287969449202825040685732379632326635633418300048983634209556964867175030252399986593427857865008518171239775643235488954015082260035235036283487660366488550474516338472679222048717177747614210739606052154819639691004286246240020230188651006378959767398084324322008453152063183987372973164598066860174889163715767177543295634165129243441461597670797375484554640164983017774064835500981051070425037996029762438322599385986157913795423953648261358937185717844177379683832237044491180000482549114763268386632780913610754235834240512650659409215396821697752992594864370658750560426230664402293637048067412815299294991452283113777309961811323532557633057727900060941499142193907009891170468728522049291402072655778336976688416252463974783689158463516778651386914053541081481476612718983711795850458476656130316790582555711188904501523691656768916238612527464448411081019203952981305496349455714491843585609791073272252568166553125529140639

n2 = 3627444771006641937670374103598493492277170277116493920932885955435916968318288577415856168749785331840818803112714250474056975340846972000039130600885450836486139285287969449202825040685732379632326635633418300048983634209556964867175030252399986593427857865008518171239775643235488954015082260035235036283487660366488550474516338472679222048717177747614210739606052154819639691004286246240020230188651006378959767398084324322008453152063183987372973164598066860174889163715767177543295634165129419489479581992906703549293578307256488898187992353900184420118800322552534062759653705575925115281872928967944090554962523467896972290709767538721152187005614513210255277428624583175610744256739492598420738558920178579717917167080004296928204063086948663685116578675918309866385297630728361719704990361341156140881005762465007490782078136991995257037173077806031411193484423581964394970840431076138212137582851077173111409746242976470913498571389253297470379823689833891657511115618469031966199517813387433692841129826086480794218247482240815273496487448622735466819104529863148460012391153385059278883

---

### **Simplest_ECC**

> 你有聽過橢圓曲線加密法(ECC)嗎? 如現在比特幣也是使用橢圓曲線作為其加密法
而 ECC 的安全性是建立在給你:
>
> 1. 橢圓曲線 Ep
> 2. 曲線上的一個基點 G
> 3. d倍的G
> 然後請你求出 d 是多少很難的情況下，而我們稱 d 是私鑰，dG 是公鑰
這裡讓你練習最簡單計算 ECC

已知橢圓曲線加密 Ep: y^2 = x^3 + 4788000822933941356*x + 2397163061523376848     

p = 10390178628259865209  (GF(p))
G = (4408534970541877833 , 7378937216560269627)
私鑰 d = 100
請求出公鑰: dG = (x,y)

FLAG 為 BreakALLCTF{md5(x+y)} ，也就是說假設 x = 0 , y = 1 
則 flag 是 BreakALLCTF{md5(1)} = BreakALLCTF{c4ca4238a0b923820dcc509a6f75849b}

---

### **babyRSA**

> 本題給你一個公鑰 pub.pem 和要解密的密文 flag.enc
請嘗試使用最基本的 rsa 攻擊 – 質因數分解來練習
>
> hint1: n 很小所以可以直接分解
hint2: 推薦 factordb.com ，想要本地跑也可以用 yafu

檔案：
[pub.pem](https://drive.google.com/uc?export=download&id=1s7LKSKanOzSbqhWhoABtGkrFZwtz_VsO)
[flag.enc](https://drive.google.com/uc?export=download&id=1Se73tWtAeG_VpeeggM4Uum8-J0qqT37L)

---

### **xor-magic**

檔案：
[cipher](https://drive.google.com/uc?export=download&id=1r339PtikMEgMnJ9RH7hI3e5MBhr0ziuR)

#!/usr/bin/env python3
from flag import flag

def xor(*args):
    ans = b'\x00' * len(args[0])
    for arg in args:
        ans = bytes([x ^ y for x, y in zip(ans, arg)])
    return ans

key = flag

plain = open('article', 'rb').read().lower()

cipher = b''

for i in range(0, len(data), len(key)):
    block = data[i:i+len(key)]
    cipher += xor(block, key[:len(block)])

open('cipher', 'wb').write(cipher)

## Level 2
### YANG_RSA-4
> 如有一家公司用RSA作為加密訊息使用，其先產生兩個非常大的 p 和 q ，然後算出 n 後，以 n 生成很多不同的公鑰-私鑰給員工，從這裡可以看到 n
>
> 重複使用下，就有可能出現共模攻擊，本身也是一種廣播攻擊。
>
> 請利用共模攻擊解密附件。
>
> 提示1 : 可以參考此篇文章說明
https://crypto.stackexchange.com/questions/16283/how-to-use-common-modulus-attack
提示2 : 也可以參考此篇簡報第34頁的函數
https://www.slideshare.net/ssuseraba268/rsa-in-ctf

#!/usr/bin/env python
from Crypto.Util import number
import libnum

p = number.getPrime(1600)
q = number.getPrime(1600)
n = p * q

e1 = number.getPrime(512)
e2 = number.getPrime(512)

m = libnum.s2n(open('flag').read().strip())

c1 = pow(m,e1,n)
c2 = pow(m,e2,n)

with open('output.txt','w') as f:
	f.write('n = %d \n\n' % n)
	f.write('e1 = %d \n\n' % e1)
	f.write('c1 = %d \n\n' % c1)
	f.write('e2 = %d \n\n' % e2)
	f.write('c2 = %d \n\n' % c2)

n = 601079890037987604431299524604731926071028289714726325853160560822671656672435372422576831180720643755002522349232818450429861500646197062814617330443684235014072184166957803892385199122293587039674209300946383069422025584266381942233078984155793427549685573859988475888412265342970813238059596786787726537911926819530604506451125553192260570386165641188535428166442552194316166923180962521164985215427597102736331300655293153400150333265029368210022213821641355315765165160575924342098863168232177127592546541673292314097366431474533263402112899677852636579661059026081681362887721283820517246291325501590627370903464556352593996466395596703609515756817330200509325258443030773008998508183500802902995673573898878264148773130870857827804095652545116545220268517058077827666474665032138823605624731794285434772957308460566796728714912951423416600299440344847642523901665983827164682786888788009473126538180992204754454924702201128344623836080923997277509247815993

e1 = 9405172090867429167522098902370749942248783790897104683679576493285386831759923838256124796722772712748691601513080032494804780492783260329501965883487449

c1 = 314564217302500200163759194260307839612780113900510659153559994404616233480977901081457219754701436603071046288000515552874294832582078073029908088537206127804857317570661216485480824510676318602134918119497217616722217174492657585743425124324907518649050736733207674535351855501078377195724227557781044380284792016437708580643509685246825169537653244291413420860826461482786045694551841250154752831892803997686933358830881165202213705675567254258355536168864546096585003491156446528289098171464737969907311920151343401576297553073358616531239922292236598022573879617946865136850496267767392774321261208975997120995221104766187122831500354603374561481266350294614422561126906570941980870039995358850974794393980407489204820700624300046702300701395126669428361520630043416955672898292369148908985504063716178629319516455430033390711455943419623574412135759361201047051736309026022515055418451530574539575536836664360617505814472330359018776028176730183083132708449

e2 = 7095565993271201701012700380853978907656102167234011354220093122363055999144351553656782816939748882018682837387651451192207734678816900790888793405286989

c2 = 231454535634498981606804851249268972673565707091933518210376565934116042099763364768783318579394065863001071012758012388779888046220585794303803977781363299140700033882412332072165508546466694644149936737091441176316685512052479450517620932425763542699912556932121122254624930817149270005252865287721155021484087246788171305870704141493508455874364528923527573135942464626727511007260700119374884220390067900433849409633808845764301976479013370962776101364599847645005622330078930265786460112041493284689945296841349882069189318814764669930730356315943075593805608591847059144964078117070976633698053027833770233512967762552688778510572408743102454627944221473329378344576994239421959385787556811017060321709056461254892708398556778100555192544461572784992678053844380781805360413711742586700791882806136633296551922581431775955348872645753475792127252625290521427755906342341946264099004311435719226771725446922256895733539634456628491176695552090922403849365718

---

### babyDSA

> alice 和 bob 目前正在熱戀中，bob 覺得是時候該結婚了，也經由路邊看起來很可靠的算命師說今天適合求婚，不論是何種方式都可。奈何 bob 今天早上臨時被公司外派出去無法趕回來見alice ，只好委託他最要好的朋友 Eve 幫他把他的求婚訊息拿給 alice ，為怕中途出現任何意外，bob 特地使用了 DSA 做數位簽章，以防止他人竄改訊息，而其實Eve也深深愛著 bob 而不想他跟 alice 結婚，所以打算偽造bob 要給 alice 的訊息。

> signed.txt 是 bob 要給 alice 的訊息
signature 是 bob 對 signed.txt 做 dsa 得到的數位簽章
need_to_sign.txt 是 eve 想要偽造傳給 alice 的訊息
code.py 是 eve 偷偷得到 bob 使用 dsa 做數位簽章的整個程式碼
public.pem 是 bob 的公鑰

> 請你想辦法獲取 bob 的私鑰來重新對 need_to_sign.txt 做簽章 。
>
> FLAG 為 BreakALLCTF{md5(r + s)}
意即如果你對 need_to_sign.txt 做簽章得到 r = 1 , s = 2 ，則 FLAG 為BreakALLCTF{md5(3)}

檔案：
code.py：

# code.py
#!/usr/bin/env python
from Crypto.PublicKey import DSA
from Crypto.Hash import SHA
import libnum
import random

priv = DSA.importKey(open("privkey.pem").read())
pub = DSA.importKey(open("public.pem").read())
m = open("signed.txt","rb").read()



def nonce(alice, bob):
	a = libnum.s2n(alice[:8]) 
	s = libnum.s2n(bob[:4]) 
	random.seed(a^s) 
	return a*s + random.randint(a+s,a*s)


def sign_msg(msg):
	alice = open("./alice.png","rb").read()
	bob = open("./bob.jpg","rb").read()
	k = nonce(alice, bob)
	h = SHA.new(msg).digest()
	r = pow(pub.g,k,pub.p) % pub.q
	s = libnum.invmod(k,pub.q)*(libnum.s2n(h) + priv.x * r) % pub.q
	sig = (r,s)
	return sig

sign_file = sign_msg(m)

with open("signature","wb") as f:
	f.write(str(sign_file).encode())

need_to_sign.txt：

It's over between us. I don't love you anymore. Bitch
signed.txt：

Would you be my wife? I want to be with you forever
[public.pem](https://drive.google.com/uc?export=download&id=18NgCecAx5jLOBuGp13JlgC8vItIh3JeF)
[signature](https://drive.google.com/uc?export=download&id=1ZMvTeDFQqX0ORwvo5a0sPwYNwJVKW6tr)

---

### **babyDSA_Part2**

> 雖然 Alice 收到來自 eve 幫忙拿來的 bob 訊息的當下花容失色，但他轉念一想又覺得事有蹊俏想來也有可能是 bob 的數位簽章被人竄改冒用了，還是自己傳訊息問她吧。也有可能是eve 在途中搗亂，畢竟 alice 也知道 eve 也暗戀bob ，而自己的數位簽章比bob 強，應該是不會被冒用的。
>
> 好了，這次也請你幫忙 eve 來破解 alice 的數位簽章吧。
>
> signed.txt 是 bob 要給 alice 的訊息
signature 是 bob 對 signed.txt 做 dsa 得到的數位簽章
code.py 是 eve 偷偷得到 alice 使用 dsa 做數位簽章的整個程式碼
public.pem 是 alice 的公鑰
>
> FLAG 為 BreakALLCTF{md5(x)} ， x 是 alice 的私鑰

檔案：
code.py：

# code.py
#!/usr/bin/env python
from Crypto.PublicKey import DSA
import hashlib
import libnum
import random
import os

random.seed(libnum.s2n(os.urandom(16)))
priv = DSA.importKey(open("priv.pem").read())
pub = DSA.importKey(open("pub.pem").read())

q = pub.q
p = pub.p
g = pub.g
x = priv.x

def nonce(state=False):
	a = 154652299970028301598774124374065456658
	b = 206934944555728541606690634601345818506
	x = random.randint(a+b, a*b)
	if state:
		return (a*state + b) % q
	else:
		return (a*x+b) % q

def sign(m, k):
	h = int(hashlib.sha256(m).hexdigest(),16)
	r = pow(g, k, p) % q
	s = int(((x * r + h) * libnum.invmod(k, q)) % q)
	return (r, s)

sign1 = open("sign1.txt",'rb').read()
sign2 = open("sign2.txt",'rb').read()
initial = nonce()
k1 = nonce(initial)
k2 = nonce(k1)
sig1 = sign(sign1, k1)
sig2 = sign(sign2, k2)

with open("signature_1", "wb") as f:
	f.write(str(sig1).encode())

with open("signature_2", "wb") as f:
	f.write(str(sig2).encode())

sign1.txt：

Eve say that you want to break up with me ?
sign2.txt：

I can't believe what Eve tell me ... .

Are you free tomorrow ?

I am free all day tomorrow ...

[signature_1](https://drive.google.com/uc?export=download&id=114HYrN-2r6OpZQxqxCAIOGm4dI4dA0Hl)
[signature_2](https://drive.google.com/uc?export=download&id=1S5XNzC1JB3SfGOnaElaESXjml9guqtRx)
[pub 2.pem](https://drive.google.com/uc?export=download&id=1smp0Sehe96UK1o1lkbOTc8sePBtDAJYM)

---

### **babyDSA_Part3**

> 有情人終成眷屬，最終 alice & bob 誤會解開，也明白是 eve 搞的鬼。
>
> 現在他們兩人正在恩愛的傳訊息，你能幫忙 Eve 再一次獲取他們的私鑰嗎?
>
> FLAG 為 BreakALLCTF{md5(x)} ， x 是私鑰
>
檔案：
code.py

# code.py
#!/usr/bin/env python
from Crypto.PublicKey import DSA
import hashlib
import libnum
import random
import os

priv = DSA.importKey(open("priv.pem").read())
pub = DSA.importKey(open("pub.pem").read())

q = pub.q
p = pub.p
g = pub.g
x = priv.x

def nonce():
	random.seed(libnum.s2n(os.urandom(16)))
	k = random.randint(libnum.s2n(os.urandom(16)), libnum.s2n(os.urandom(20)))
	return k

def sign(m, k):
	h = int(hashlib.sha256(m).hexdigest(),16)
	r = pow(g, k, p) % q
	s = int(((x * r + h) * libnum.invmod(k, q)) % q)
	return (r, s)

sign1 = open("sign1.txt",'rb').read()
sign2 = open("sign2.txt",'rb').read()
k1 = nonce()
k2 = k1 +  pow((nonce() & 0xffff >> 4 ),(k1 >> 6 | 0xffff) ^ (k1 >> 6 | 0xffff))


sig1 = sign(sign1, k1)
sig2 = sign(sign2, k2)

with open("signature_1", "wb") as f:
	f.write(str(sig1).encode())

with open("signature_2", "wb") as f:
	f.write(str(sig2).encode())

sign1.txt：

I love you , Alice
sign2.txt：

I loce you , Bob

[pub.pem](https://drive.google.com/uc?export=download&id=1OvihdbpNYhcIxDhE9V_re7DrLVoqTa3A
)
[signature_1](https://drive.google.com/uc?export=download&id=1UR9fZSTNU6E4tyIH310UVSMmMs_ZeSTP)
[signture_2](https://drive.google.com/uc?export=download&id=16Frh-aOKOxgsitelscFzPJmERPC0kCY0)

---

### **babyDSA_Part4**
> Alice & Bob 覺得好像私鑰又被破解了，思考後覺得是因為使用複數 k 之後，因為有一些線性上的關係所以出問題，這次他們只使用一個 k ，應該就沒問題了吧 ?
>
> 你能證明他們是錯的嗎?
>
> FLAG 為 BreakALLCTF{md5(x)} ， x 是私鑰

檔案：
code.py：

# code.py
#!/usr/bin/env python
from Crypto.PublicKey import DSA
import hashlib
import libnum
import random
import os

priv = DSA.importKey(open("priv.pem").read())
pub = DSA.importKey(open("pub.pem").read())

q = pub.q
p = pub.p
g = pub.g
x = priv.x

def nonce():
	random.seed(libnum.s2n(os.urandom(16)))
	k = random.randint(libnum.s2n(os.urandom(16)), libnum.s2n(os.urandom(20)))
	return k

def sign(m, k):
	h = int(hashlib.sha1(m).hexdigest(),16)
	r = pow(g, k, p) % q
	s = int(((x * r + h) * libnum.invmod(k, q)) % q)
	return (r, s)

sign1 = open("sign1.txt",'rb').read()
sign2 = open("sign2.txt",'rb').read()
k = nonce()^nonce()
sig1 = sign(sign1, k)
sig2 = sign(sign2, k)

with open("signature_1", "wb") as f:
	f.write(str(sig1).encode())

with open("signature_2", "wb") as f:
	f.write(str(sig2).encode())

sign1.txt：

Hey,sweety,sorry,I’m late again
sign2.txt：

I hate you!I can’t stand you any more,you always stand me out!
[pub.pem](https://drive.google.com/uc?export=download&id=1sHDN9Qi5xtbazr4UPj917ddi1SXaeaSl)
[signature_1](https://drive.google.com/uc?export=download&id=1nPMMxLxUbqH9ujzCFg8hfI6iV2v88ae-)
[signature_2](https://drive.google.com/uc?export=download&id=1GrpOkft6MPpSSQRm8JMKF5METq5m_zjg)

---

### **BasicSmooth**

> 如果使用橢圓曲線密碼學時，其 order 可以被分解為多個小質數的話，則會有被攻擊成功的風險存在

已知橢圓曲線加密 Ep: y^2 = x^3 + a*x + b (mod p)

a = 300863890703896560332832537955553678141
b = 268697897483481153104248486036866865253                               
p = 949174172520272387583695902445009966758689857140427760296021  (GF(p))

基點 P = (253707595978034699490249605504317581406206458257142863931074 , 737036330622356659355872744217474772666331295402861579985162)
私鑰 d = ?

公鑰: G = d*P = (143765641554022797060750639992948892251346023192973138033948 , 767645821458610691542705360647817899757826465509229385191533)

FLAG 為 BreakALLCTF{d} 

備註: d < 6096200200

hint: Pohlig-Hellman Algorithm

---

### **CBC**
> 來練習一下 CBC bit-flipping 吧
nc 140.110.112.30 4120

problem.txt：

#!/usr/bin/env python3
import os
from base64 import b64encode, b64decode
from Crypto.Cipher import AES

flag = open('flag', 'r').read()
key = os.urandom(16)

def pad(data):
    k = -len(data) % 16
    if k == 0: k = 16
    return data + bytes([k] * k)

def unpad(data):
    return data[:-data[-1]]

def encrypt(data):
    iv = os.urandom(16)
    aes = AES.new(key, AES.MODE_CBC, iv = iv)
    return iv + aes.encrypt(pad(data))

def decrypt(data):
    iv, data = data[:16], data[16:]
    aes = AES.new(key, AES.MODE_CBC, iv = iv)
    return unpad(aes.decrypt(data))

print(b64encode(encrypt(b'A' * 32)).decode())

cipher = b64decode(input().strip())
if b'CTFGOGOGO' in decrypt(cipher):
    print(flag)

---

### **ECB**
> 來練習一下 ECB cut&paste 吧
nc 140.110.112.30 4121

server.py：

#!/usr/bin/env python3
import os
from base64 import b64encode, b64decode
from Crypto.Cipher import AES
from flag import flag

key = os.urandom(16)

aes = AES.new(key, AES.MODE_ECB)

def pad(data):
    k = -len(data) % 16
    if k == 0: k = 16
    return data + bytes([k] * k)

def unpad(data):
    return data[:-data[-1]]

def encrypt(data):
    return aes.encrypt(pad(data))

def decrypt(data):
    return unpad(aes.decrypt(data))

def register():
    username = input('username: ').strip()
    if 'admin' in username:
        exit()
    password = input('password: ').strip()
    token = encrypt(f'username:{username};password:{password}'.encode())
    print(b64encode(token).decode())

def login():
    token = decrypt(b64decode(input('token: ')))
    username, password = token.split(b';')
    if username.split(b':')[1] == b'admin':
        print(flag)

def menu():
    print('''1) register
2) login''')

def main():
    while True:
        menu()
        option = input('> ').strip()
        if option == '1':
            register()
        elif option == '2':
            login()
        else:
            exit()

main()

## Level 3

### **OWO_Nonsense-Machine**

> 有一個遠端伺服器窮極無聊，專講一些五四三，但在他講了很多廢話中，卻有一個是你要的flag。
>
> 提示1 : pwntools可以快速連線送出訊息並取得你要的flag。
提示2 : 暴力破解似乎是唯一的方式。
>
> 連線到下列位址，破解出他的通關密語:
nc 140.110.112.30 4119

server.py：

#!/usr/bin/env python3
import os
import random
from Crypto.Cipher import AES
from base64 import b64encode, b64decode

with open("flag", 'rb') as data:
    flag = data.read().strip()

key = os.urandom(16)
def generate_counter():
    counter = random.randint(0,99)
    return counter.to_bytes(16, 'little')

def encrypt(message):
    aes = AES.new(key, AES.MODE_CTR, counter = generate_counter)
    return b64encode(aes.encrypt(message)).decode('ascii')

print("===== Welcome to nonsense machine =====")
print("Here is your flag : {}".format(encrypt(flag)))
print("Now I am going to talking nonsense")
print("You also need to tell me some nonsense")

while True:
    print(encrypt("nonsensenonsense"))
    input("your turn : ") # I don't care what you said XD

---

### **SECCON2017_Ps and Qs**

> Ps and Qs
Decrypt it.
>
> psqs1-0dd2921c9fbdb738e51639801f64164dd144d0771011a1dc3d55da6fbcb0fa02.zip (pass:seccon2017)

[psqs1.zip](https://drive.google.com/file/d/1MUHee_sWnVQtk1jHFvA_34Wg8AiwwCwj/view?usp=sharing)

---

### **rsa_known_p_high_bit**

> Code.py 是小明實作 rsa 的整個流程，在部分資訊洩漏的情況下，你有辦法解密嗎?
推薦工具: Sage

N = 22838960456421139208541144997446589236388152104301416644229227629463979063658890632209891439139888443259700039249459716854443727413442318448614788154483848660624621958689637653344984169796089902646052228536164396406557864762046692930673150406297782501442747669434467674752193772987427925523987516304671768036460639490362549001638710740311882014714898506488484077789234138400806779314957572243557386122954643660901208496696659630062897778560202517175743163041838540763904845685205648016360794823430818100775409536294724573825070302903069380915273907360597950163551619974290032737940420590599704559341054254599943188543
e = 65537
leak_info = 136134883199125664402919304347145218160348405219117695475270368050419780117740420921873479736982994286078118114849450601432412648851586371377994711652066051282723804633308565405432072345021147854801822690634740270782164339963839172327446982860860009869931898979226690257553221155608620457253941390351540420608
c = 9965610123442815316032547609712501398994089156156428079250077197986413712782149159671280942603184118330937761502655582876711105374166883098455660086551947766346069362173041779119352900119749820814734615667588447609589048778621539799776072676116400653401549059499463601119067807520845445110205427103372270093413492042201018813502892691972286751350629696926139742399092775421956586597971973878316060952035501246475652155915301583460117636255579936109556308096724315317531722876232639001239066899994618429184680398611936107406281785542637752485986496996735063018797008857387353391779337341176676267503986787396352694928

# code.py
#!/usr/bin/env python
from Crypto.Util.number import *
import libnum

m = libnum.s2n(open("flag.txt",'r').read()) 
e = 0x10001
p = getStrongPrime(1024, e)
q = getStrongPrime(1024, e)
n = p * q
c = pow(m,e,n)
leak_info = ((int("0x" + (len(hex(libnum.nroot(n,4))) - 30) * "f", 16) & p ) ^ p)

result = "N = %d\ne = %d\nleak_info = %d\nc = %d" % (n, e, leak_info, c)

with open("problem.txt",'w') as f:
	f.write(result)

---

### **common_factor_attack_rsa**

> 小明剛剛學會了 rsa ，所以他很興奮的寫了一下程式來實作 rsa 的過程
>
> 但他不小心把他的明文(flag.txt) 給搞丟了， code.py 是小明實作 rsa 的程式碼
你能幫他找回遺失的明文嗎?

# code.py
#!/usr/bin/env python
from Crypto.Util import number 
import libnum
import random
import itertools
flag = libnum.s2n(open("flag.txt",'rb').read())
e = 65537
n_size = 2048
prime_list = []
n_list = []

for _ in range(50):
	prime_list.append(number.getStrongPrime(n_size, e))

for i in itertools.combinations(prime_list, 2):
	n_list.append(i[0] * i[1])
random.shuffle(n_list)

result = ""
for n in n_list:
	result += str(pow(flag,e,n)) + "\n"
with open("ciphertext.txt","w") as f:
	f.write(result)

[ciphertext.txt](https://drive.google.com/uc?export=download&id=1LwFrID7Pb_mg1kiF8phBYtXyaicFgtwA)

---

### **rsaHOT**

> 在 rsa 中，如果使用同一把公鑰對有線性關係的明文作加密，則可以對其作破解
>
> 而在 d 小於 1/3 n 的 1/4 次方時，則可以藉由還原出 phi(n) 來求得 d
>
> 推薦閱讀:
https://www.cs.unc.edu/~reiter/papers/1996/Eurocrypt.pdf
https://en.wikipedia.org/wiki/Wiener%27s_attack

#!/usr/bin/env python
from Crypto.Util.number import *
import libnum
import random

def enc1(bits, msg):
	p = getPrime(bits)
	q = getPrime(bits)
	e = 3
	n = p*q
	assert msg < n
	msg2 = e*msg+libnum.s2n("BreakALLCTF")
	c1 = pow(msg, e, n)
	c2 = pow(msg2, e, n)
	return (c1, c2, n, msg^msg2)

def trans(num, mix, bits):
	mix = int(pow(2,bits-1)) + mix
	for i in range(10000):
		tmp = mix + i
		if isPrime(tmp) and libnum.gcd(tmp, num) == 1:
			break
	assert tmp > 2**(bits-1) - 2**(bits//2) and tmp < 2**(bits-1) + 2**(bits//2)
	return libnum.invmod(num, tmp)

def cal_ed(p, q, mix):
	phi = (p-1) * (q-1)
	bits = size(p*q)
	while(1):
		r = getPrime(bits // 5)
		if libnum.gcd(r, phi) != 1:
			continue
		x = libnum.invmod(r, phi)
		e = trans(x, mix, bits)
		if libnum.gcd(e, phi) == 1:
			break
	d = libnum.invmod(e, phi)
	return (e, d)

def main():
	result = ""
	bits = 1024
	c1,c2,n,mix = enc1(bits, random.randint(pow(3,bits/4), pow(2,bits/2)))
	result += "c1 = %d\nc2 = %d\nn1 = %d\n\n\n" % (c1, c2, n)
	pqbits = size(mix)*3
	flag = libnum.s2n(open("flag.txt", 'r').read())
	p = getPrime(pqbits)
	q = getPrime(pqbits)
	n = p*q
	e, d = cal_ed(p, q, mix)
	c = pow(flag, e, n)
	result += "c = %d\ne = %d\nn = %d\n" % (c,e,n)
	with open("problem.txt","w") as f:
		f.write(result)

main()

[problem.txt](https://drive.google.com/uc?export=download&id=19Gnsc3HIBLa7E2qIaUdYTShiy_Tu_6Wf)

## Leve 4
### **YANG_RSA-5**
> 中國剩餘定理(Chinese Remainder Theorem)又稱為孫子定理是關於一元線性同餘方程組的定理，說明一元線性同餘方程組有解的準則以及求解方法。
RSA產生金鑰的過程中，有要求 gcd(e,phi) = 1 ，這樣才可以算出 d。
而本題故意使 gcd(e,phi) != 1 ，所以不可以照常規的方式去解，可以把所有得到的資訊組合起來，會發現符合中國剩餘定理，並可以以此去解密。
>
> 請利用中國剩餘定理解密附件。
>
> 提示1 :
假設 m = 明文 ， c = 密文
m^3 % p = c % p
m^3 % q = c % q
m^3 % r = c % r
這樣可以透過中國剩餘定理去解題目
提示2 :
算數學可以參考使用以下網站
http://www.wolframalpha.com/

檔案：
[YANG_RSA-5](https://drive.google.com/uc?export=download&id=16daB-fzbt8WmPAf9rdXcZWxQDqS3kDeG)

---

### **AIS3_Pre_exam_2016-Crypto3**

[crypto3.tbz](https://drive.google.com/uc?export=download&id=15dqRkOEi7fMdU0dHE08ombIOZrknp0dV)

---

### **OWO_Apple Shop**
> 快來買些蘋果吧?蘋果專賣店有你要的flag。
你必須兌換coupon得到錢來買 flag。
coupon 有分100, 500, 2000 元，一開始使用者有一張free coupon可以兌換100 元(coupon只能用一次)。
>
> 提示1:你知道Length_extension_attack嗎?
請參看維基百科的說明
https://en.wikipedia.org/wiki/Length_extension_attack
提示2:hashpump可以幫助你解題。
>
> 請連線到下列位址解題:
nc 140.110.112.30 4118

[server.py](https://drive.google.com/uc?export=download&id=1vIjksdlT7biCnP9VfOhD_K-ZT0shar6_)

---

### **RSA 後門 (1)**

> 這是一個RSA 的題目，提供一個後門給你，你能否解密呢?
提示1: RSA 模運算觀念，可以參考
https://simple.wikipedia.org/wiki/Modular_arithmetic
提示2: Fermat-euler theorem
http://wsfdl.com/algorithm/2016/02/11/理解RSA算法.html

n = 760070912350840319011516178942471824408271276603018122766107466458905659805366910876741133101064132968975290327141913870064382857896676965896339499301686289349478192042225387715815300890772726396671069777379993317290403468858998199888875329375096856205675179863574081470688602128633185902300536380591686253782626310388376732381905094112550405708724116437892957067685087277238106233348311268725082471734753857194847838970086800848099069387690801700501505622593836970903856921989336476413802534078525413311063453348054161408156303570666333425678334142525184422436235677229592264286240481233065103525594733333609350428196011268071126676023443256564227488106063073893805882904030218186925942692848016877882566240601003792167543787342287123520711449083265386813671510310650585456131441220450039511889734856795425972738718472877437781909089006687000385532764327586589650518853864825005505232375529254511923368560433385960598232647516144607822711918385784586608803888123523660880157194471094579495414720939362559417376095025821133997982361566429601158965282863289774835745836514384219847770664031196660782737380240398358478721495348483958183701077510621561366810555045657804658889409015678773329196458757404769771384361180527520601391357800258141800488661477548160080188323687255844523623758493111371703516522245476661361074371234254770474249888532163823739762576169486427817071850060196906194007205553628806031759720577392913205266258974893510396850982203198212807648844222854214722691172053026220943259272390113639543712309874760232956983371190047789729422160337209334177864706118802632248174293863932718038360834909893547570166552708085714105225222230703430768672212375445000147155804641468351838745755024401386395525712050470895155325019568159034388240484857157405320152956355210692650494136549140160597175749
e = 65537
c = 23043402590987555987470005871777877151151322716060092459929038792187374705968922913981882558830225470321029330756473052187571435747992606303872345391192250986189523554344860876217195521571582376245238947762932906008745950998260974696231231824601028638289006875327541511759557000571143570848503096379667666967042396170909355179367747237803420662010299628257013342744836612954085028392265365961440279234959713291284949713775237855329413455655772310421877970592292542102538256515263604910522531928228880078584842456141579974665432527149970116608055188948668252221996589209114900583773037478077453666787948360947075322921408423852746262833539233406967548960178792506005300931929791663889585748150722426246846945324183653314928671217591271109921760823893150502841856609499818424934712192715672939108605032696495577793313699830025230983849952517890751090570666447986086847837086779757192278809702226557559967552406759613743288491173421943288898163371672471990115969010871440555604481217266874916781598035536414979414464006324273200204670733327544831907946399527743271591693219872979511671485433003231621892498425559325421320388096593342519672705301186660848415575840192111782413754304841694673552200242842522814616994132736554544962232150040663460968513256281961794248016394841074724067661800839577955360386734635675931880822030409894997770620409228346807030968725967258287589342081617955999751395789800908644912870435347895906209405598557569815132825199794518175327458521867303551685164794679068776727276119468526737538107724423172989004606420592240046923867223729763034260869375338820559888057264343970350523466971697923158383084508306076913151571967057252009643027901618887695230860718585529467899380034905236786873876780870273574985011685074373247696219994297416533789436191368362809767858885056459978807647
d^2*e + 7phi = 1620126254178307107805925347409210109079418631271539038205383853825500296811505131321875475715376307920981259462614357533466941753203754184389902040317390296735523174111832078921071210983364802271706444506677317213375748433529142733682590086434843883159602424571840661084006789837565204356906806127384353403137070496607341705255529168928432860284811151663733497947457852894849483010205070190430044884550533111192278310167522337536246523319753834614895078829866621645079609537944800585691132921447071067406128053795992296555789860705164267117376403341249194265381912880381122911987670787720090648797468392804379581428828927625443096354958698305106425356304804759341769351628590201355981787898026961417197010017978586896498369566391766916389949150734429923140437868014851873995161973857943326484813660496439427382145248573160747328757222766985442936636962614338471082462176542018466676085655454126951355550126361556257104662075266568603316336712255778109160502274520531194415105288138253088913783390737905518421815608069570180353522268625980073518750189827406619294497755771287793106258255192904299584048308228213978894683176026406779635394795370495734518744326300256193256380087951019044375347232461900888446065009489097640645391262386569608187845289178411183302612154855933859365795959462296302969045375802007650006363182447142282246172159815897175833698776663254485330016779371149328376513575569112760942981544834502925172841196048299545002337578813030918604554192291352785887470669511311646710910107563532165621630764987769666815016543655079038651842299906822911300266765706794298700862048041414816161796925300877951583684498109038799176817515156155043226336378501966674335980213598353300400499799267983331829293506615875633931684214060079961057050811529994328542272465237370490978257671901267949207368118469813482528549191337691272398251984525988911374674261415802154066814829811852235633680796855638371608427840349392807069113908188523610318541628405008514061483659101476049254558271853247155909822423178322733169352572052726772582248896209811295644754652929887794307253538519583308522548764807171997390978930362807674618922673784345674399280165757903254849166255862761505958877746491695638693225723742471994074977722764774396977099203362493734497024157950664679560033045482790511829641981266050781145047063439829017411287025152601657710843117158464125963489235207735032378012469116305985018154124770869140988608396527280659847552980183759392006298043098302142036369831264210519529460144456046718107048666133409389414971293612254496187041396109788710182456978219643383191376104152139390281682725843970462663476429188678725076567909771351453134707771292457507252653887820906120220438288603368324527890395568883849113861497960739320824870111660002336940925676213182090142135460146471543405919951993709743278922880730501901447471415221734066265696076586382009664274086330323532584722108261464690626012127056796760247870942832409248150162628837118556643673490483508340076601494462894830031383023978791318416731750735151837937806847488275195597134674111405788736045846451812924630643394346576798523225002203801819682823374228410113250193049149956290221614268899002507311843085666803688279048710674142634342181537227528937600806325860076859203781668984084015772848021783541825345156247897291696817517617346614862474694333096308102196024040585991378871897997839002740030027319532462250477445464847537717734353083321981680750712108267543263803466885591366936121859171083424502493973267513173320411368750946440514079437531574281488938077212799745537360636372874039590628648466074136236105865275970476148518382544665640833

備註:
c 是要請大家解密的密文
phi = (p-1)*(q-1)

---

### **RSA 後門 (2)**
> 在實際的情況中，可能我們替每個要加密的設備，將其產品序列號或其 MAC 位址之類的作一些轉換來得到一個值
>
>也就是後門，之後都是正常加密發送訊息。而當一些執法機構想要閱讀這些被加密的訊息時，則可以申請授權書，扣押設備並拿剛剛得到的後門來解密訊息。
>
>本題提供一個後門給你，你能解密嗎?

#!/usr/bin/env python
from Crypto.Util.number import *
from libnum import *
import random

def write_file(n, e, c, a):
	with open("ciphertext.txt", "w") as f:
		f.write("n = %d\n" % n)
		f.write("e = %d\n" % e)
		f.write("c = %d\n" % c)
		f.write("backdoor = %d\n" % a)

def gen_prime(a, bits):
	_p = getPrime(bits / 4)
	key = _p
	while 1:
		p = key*a + _p
		if isPrime(p):
			return p
		key = key + 1

m = s2n(open("flag").read())
e = 65537
bits = 512
a = getPrime(bits*3//4)
p = gen_prime(a, bits)
q = gen_prime(a, bits)
n = p*q
c = pow(m, e, n)

write_file(n, e, c, a)

n = 50369705985482585847076174369853821603154303310106327807868712479743694221457339242884498113243060856069808087782933234999765171016806263293719168918823711958115798881543855324333978052814883370501198510805289317130833839313787714359975510471914488525336183114435259907705143350519169852249375161865277594997
e = 65537
c = 34969764551688203712071798683614187901475727932560784692814181187345594420384791625240935569228222863927863600230521126662144055379579857327138388191739351845710366303194437097705737618522435025781830557579796490476054317749229046579843056391122502197482812965090655614305107942376528620831758328733429938102
backdoor = 33373869632069931959699879805778889754924367483756485586804493569660263376128265584480772385621062595818608366868117