#chall1.pyfrom Crypto.Util.number import long_to_bytes
import random
secret = open("secret.png","rb").read()
a = random.randrange(256)
b = random.randrange(256)
r = random.randrange(256)
x = random.randrange(256)
enc = 0for s in secret:
enc <<= 8
x = (a*x+b)%r
enc += s^x
f = open("encrypted_data.dat","wb")
f.write(long_to_bytes(enc))
prime connect
prime + prime = prime
添付ファイル：prime_connect.py
from Crypto.Util.number import *
defencrypt(st_len,go_len,prime,message):
s = 0
l = 1
c = []
while st_len <= go_len:
whileTrue:
q = getPrime(st_len)
qbin = bin(q)[2:]
whilelen(qbin) < st_len: qbin = "0" + qbin
next_prime = int(bin(prime)[2:] + qbin,2)
if isPrime(next_prime):
N = prime * q
m = bytes_to_long(message[s:s+l])
e = 101if prime%e != 1and q%e != 1:
c.append(pow(m,e,N))
prime = next_prime
break
st_len *= 2
s += l
l *= 2assertlen(message) == s
return c,N
flag = open("flag.txt","rb").read()
gen_p = getPrime(16)
c,N = encrypt(gen_p.bit_length(),256,gen_p,flag)
print(c)
# [923347949, 7382279973222128877, 122962146306170765837908848551223454567, 3549519152212014068083700234235160186300219130505299139696292306205464039799, 1527384673643022720120101064151977796913895264858932377772580237410767118686969106391529500139242897405662607203540127567551879700554668904837212450683883]print(N)
# 6159034900797898425838526763919325877394844976323736393192254250464963575156530328240421294138007406960476709427205843365628191563244980986067184889098833
import random
from Crypto.Util.number import *
secret = open("secret.png","rb").read()
flag = open("flag.txt","rb").read().strip()
assertlen(flag)%3 == 0
ex = random.randrange(len(secret)-1)
e = bytes_to_long(secret[ex:ex+2])
p = getPrime(256)
q = getPrime(256)
n = p*q
c = []
for i inrange(0,len(flag),3):
m = bytes_to_long(flag[i:i+3])
c.append(pow(m,e,n))
print(c)
# [6298113965475853786056847106208713300642945466885637995557170104494725950616074542425506023987217363886529665397919957618261581053133941027535155746435321, 135028125411958273916880824261545147614327725922209748340303390558194571689687977032589044265126382565916547879777234892642296715526896605761082569309957, 1321747274929612152457518915168588918356514442679554382787182364164828302372180029740168631933681540647333144180952171045221159999310072594994307374026397, 2918560933591924342981380338403848413183651470512194619662681532592047008257668515013412096463534685052633599782673614961906361066771670231196673146753898, 5775447489821919812656223325306418654099675333689382733144673190079859607549709791366025032709099098614570746711061453405145141567455154943434221193937600, 1274850466517264624838781305598541289691584629758963818109637778738466734330749252973718909288129468236472225834841856001947077472220670167226069634313329, 1303782230905842229285244210919421873678385109856332605169575017604438212677510463647334165086069519414714376999894517045356733235945921910952902514007317]
tadpoles only know the alphabet up to b... how will they ever know what p is?
添付ファイル：tadpole.py, output.txt
#tadpole.pyfrom Crypto.Util.number import bytes_to_long, isPrime
from secrets import randbelow
p = bytes_to_long(open("flag.txt", "rb").read())
assert isPrime(p)
a = randbelow(p)
b = randbelow(p)
deff(s):
return (a * s + b) % p
print("a = ", a)
print("b = ", b)
print("f(31337) = ", f(31337))
print("f(f(31337)) = ", f(f(31337)))
a = 7904681699700731398014734140051852539595806699214201704996640156917030632322659247608208994194840235514587046537148300460058962186080655943804500265088604049870276334033409850015651340974377752209566343260236095126079946537115705967909011471361527517536608234561184232228641232031445095605905800675590040729
b = 16276123569406561065481657801212560821090379741833362117064628294630146690975007397274564762071994252430611109538448562330994891595998956302505598671868738461167036849263008183930906881997588494441620076078667417828837239330797541019054284027314592321358909551790371565447129285494856611848340083448507929914
f(31337) = 52926479498929750044944450970022719277159248911867759992013481774911823190312079157541825423250020665153531167070545276398175787563829542933394906173782217836783565154742242903537987641141610732290449825336292689379131350316072955262065808081711030055841841406454441280215520187695501682433223390854051207100
f(f(31337)) = 65547980822717919074991147621216627925232640728803041128894527143789172030203362875900831296779973655308791371486165705460914922484808659375299900737148358509883361622225046840011907835671004704947767016613458301891561318029714351016012481309583866288472491239769813776978841785764693181622804797533665463949
modulusを求める問題です。0 mod pとなる式を二つ作りgcdを取ります。今回はgcdがそのままmodulusとなりました。
#solver.pyimport math
from Crypto.Util.number import *
a = (中略)
b = (中略)
f = (中略) #f(31337)
ff = (中略) #f(f(31337))print(long_to_bytes(math.gcd(a*31337+b-f,a*f+b-ff)))
i hope you're feeling lucky today
nc be.ax 31800
添付ファイル：luckyguess.py
#luckyguess.py#!/usr/local/bin/pythonfrom random import getrandbits
p = 2**521 - 1
a = getrandbits(521)
b = getrandbits(521)
print("a =", a)
print("b =", b)
try:
x = int(input("enter your starting point: "))
y = int(input("alright, what's your guess? "))
except:
print("?")
exit(-1)
r = getrandbits(20)
for _ inrange(r):
x = (x * a + b) % p
if x == y:
print("wow, you are truly psychic! here, have a flag:", open("flag.txt").read())
else:
print("sorry, you are not a true psychic... better luck next time")
you could make an exchange out of this
添付ファイル：exchanged.py, output.txt
#exchanged.pyfrom Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from secrets import randbelow
p = 142031099029600410074857132245225995042133907174773113428619183542435280521982827908693709967174895346639746117298434598064909317599742674575275028013832939859778024440938714958561951083471842387497181706195805000375824824688304388119038321175358608957437054475286727321806430701729130544065757189542110211847
a = randbelow(p)
b = randbelow(p)
s = randbelow(p)
print("p =", p)
print("a =", a)
print("b =", b)
print("s =", s)
a_priv = randbelow(p)
b_priv = randbelow(p)
deff(s):
return (a * s + b) % p
defmult(s, n):
for _ inrange(n):
s = f(s)
return s
A = mult(s, a_priv)
B = mult(s, b_priv)
print("A =", A)
print("B =", B)
shared = mult(A, b_priv)
assert mult(B, a_priv) == shared
flag = open("flag.txt", "rb").read()
key = sha256(long_to_bytes(shared)).digest()[:16]
iv = long_to_bytes(randint(0, 2**128))
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
print(iv.hex() + cipher.encrypt(pad(flag, 16)).hex())
p = 142031099029600410074857132245225995042133907174773113428619183542435280521982827908693709967174895346639746117298434598064909317599742674575275028013832939859778024440938714958561951083471842387497181706195805000375824824688304388119038321175358608957437054475286727321806430701729130544065757189542110211847
a = 118090659823726532118457015460393501353551257181901234830868805299366725758012165845638977878322282762929021570278435511082796994178870962500440332899721398426189888618654464380851733007647761349698218193871563040337609238025971961729401986114391957513108804134147523112841191971447906617102015540889276702905
b = 57950149871006152434673020146375196555892205626959676251724410016184935825712508121123309360222777559827093965468965268147720027647842492655071706063669328135127202250040935414836416360350924218462798003878266563205893267635176851677889275076622582116735064397099811275094311855310291134721254402338711815917
s = 35701581351111604654913348867007078339402691770410368133625030427202791057766853103510974089592411344065769957370802617378495161837442670157827768677411871042401500071366317439681461271483880858007469502453361706001973441902698612564888892738986839322028935932565866492285930239231621460094395437739108335763
A = 27055699502555282613679205402426727304359886337822675232856463708560598772666004663660052528328692282077165590259495090388216629240053397041429587052611133163886938471164829537589711598253115270161090086180001501227164925199272064309777701514693535680247097233110602308486009083412543129797852747444605837628
B = 132178320037112737009726468367471898242195923568158234871773607005424001152694338993978703689030147215843125095282272730052868843423659165019475476788785426513627877574198334376818205173785102362137159225281640301442638067549414775820844039938433118586793458501467811405967773962568614238426424346683176754273
e0364f9f55fc27fc46f3ab1dc9db48fa482eae28750eaba12f4f76091b099b01fdb64212f66caa6f366934c3b9929bad37997b3f9d071ce3c74d3e36acb26d6efc9caa2508ed023828583a236400d64e
mult関数を見ていきます。線形合同法のような計算をn(=a_priv or b_priv)回行います。nはかなり大きい数字のため、O(n)となる逐次処理では計算が終わりません。ゆえに、mult関数を高速化最適化を行います。
mult(s, 1) = as+b mod p
mult(s, 2) = a(as+b) + b = (a^2)s +ab + b mod p
mult(s, 3) = a((a^2)s+ab+b) + b = (a^3)s + (a^2)b +ab + b mod p
-> mult(s, n) = (a^n)s + (a^(n-1))b + (a^(n-2))b + ... + ab + b = (a^n)s + b(((a^n)-1) / (a-1)) mod p
上記のように、規則性と等比数列の和の公式を使って高速化できる式となりました。ここからn(=a_priv or b_priv)を求めていきます。つまりnの式を作るよう変形すると、
mult(s, n) = A = (a^n)s + b(((a^n)-1) / (a-1)) mod p
(a-1)A = (a^n)(a-1)s + (a^n)b - b mod p
(as-a+b)(a^n) = (a-1)A + b mod p
(a^n) = ((a-1)A+b) / (as-a+b) mod p
右辺は既知の変数のみで構成されているので計算できます。あとは、(右辺の値) = an mod pとなる値を求める過程だけなのですが、離散対数問題を解くということとなります。
暗号化
n = ppq
h = g^n mod n
c = g^m × h^r = g^m × (g^n)^r = g^(m+nr) mod n
復号
a = ((c^(p-1) mod p^2)-1) / p
b = ((g^(p-1) mod p^2)-1) / p
m = a × b^(-1) mod p
oracle
公開鍵をくれる
flagの暗号文をくれる
任意の暗号文を復号し、その下位1bitだけ教えてくれる
暗号化方式は同じで復号oracleも存在しているのですが、この問題はflag以外の暗号文は全て復号してくれるという問題でした。cをflagの暗号文とすると、c' = c2 mod nを復号してもらうと2×flagとなり、半分で割ってlong_to_bytes()していました。それにしても、1年前の自分はちゃんと復号される証明までできていたのに今は分からなくて退化してる…。
(m-1)/2 = (m-1) × 2^(-1) = (m+(n-1)) × 2^(-1) = (m+(n-1)) + (m+(n-1)) + ... + (m+(n-1)) mod n
c'' : (n-1)の暗号文
c'' = g^(n-1+nr) mod n
c' = (c × c'')^(2^(-1)) mod n
This guy keeps insulting my girlfriend! His last message confused me, though! Can you help me decode it?
/Rn/X7n#bUc.rjzh,|eEsg,?&QI;@^ARm}UKOkICi#X.ixEmN]D
A soldier was walking around the streets of Sicily, late at night, with THE Consigliere. Same soldier, the very next day, found in a ditch with a note in his breast pocket. It read:
f433c3e883a1389482c0b652660580f36ea037434fd4a67d193bc1cdc9b2cc34
Flag format: TFCCTF{secret_message}
The train to Paddington is leaving soon! Will you be able to find your ticket ID in time? Why did you encrypt it without storing the password...?
添付ファイル：main.py, output.txt
と、対角成分だけが2乗されそれ以外の値は0になりました。同様に3乗, 4乗と計算しても同じ結果となるので、output.txtにある行列の対角成分は pe mod n, flage mod n となります。
前者(pe mod n)を使って素因数分解します。具体的には、この値はpの倍数かつnの倍数ではないことが分かっているので、gcdを取るとpの値が出てきます。
素因数分解ができたので秘密鍵dを求め、(flage)d mod nを計算すればflagとなります。SECCON CTF 2021 pppp のように行列をd乗して元通りにしても復元され、問題名よりこちらの方がより想定解なのかなと思っています。
from Crypto.Util.number import *
import math
c = [(94705679004463284733541288053549635663983624426348082883911423652044420589882644740030824857964094373277293351421545117172457918484063609288563394969114856228940330220982203798491227942337707868513380987219942847139213839127934175216087451584996193094098370176337671205679032479708240220775365041028562298045, 0), (0, 14243811671300968907609174458855708829741032120754409000357686908873126315334915231420353855815283498571171729689334442024813021199910238276500626386134036150649025606319036019223959715867658461585221634071508142818645594816357236002650041503442624594820852244903155433016041077813314542285538820574629698950)]
n = 123658273021758657244926229590842169697216202161458868027271307824674005278002104678607018762498569110790554844101479136721968081586766904446085438475258864812618061595487772978115460674609635002737826341845366713797429237465562629770189347062332559337703309881797723858775511801114681134013841432780549606609
e = 65537
p = math.gcd(c[0][0],n)
q = n//p
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c[1][1],d,n)
print(long_to_bytes(m))
from Crypto.Util.number import *
from sympy.ntheory.modular import crt
x = 397
num = 2
mod = []
val = []
c = 6444384937952479446360543800306726693252997452825552613901755375099255166714791921303820142603050845604453415771813934605436773362180219243666255359716995456217503120584807127945079526447091871683834669804927783277541340212953733681665967741288390917442432418885663222080013261671274096066346531406665749671823431928515791704387207382571496076159703188939522942673142857854899106254676400171188528066441584894129954980506317784944539407501773216256651827692873203651175
e = 65537
n = 13105434584967797009222723925714056612973229654650200307281518067540513311350491750775580308761120670043385919352137451528084580772272083564644136982142743585238409901075466075590932718136237274538943262152033321299508243379729042658808185056276914453786554308920681089647171956781340126500826872053436182017911021212882822071757885385543985492728290224139575551494811781675324350095354476279621406379090030101147754502075514438702852559140941288066281245455568260855730while num <= x:
if isPrime(num):
mod.append(num)
num += 1for i inrange(len(mod)):
for j inrange(mod[i]):
if c%mod[i] == pow(j,e,mod[i]):
val.append(j)
break
m, MOD = crt(mod,val)
print(long_to_bytes(int(m)))
import math
from Crypto.Util.number import *
e = 65537
f = open("distfiles/output.txt")
a = f.readlines()
cs = eval(a[1][5:-1])
#print(type(cs))
flag_part = 'HarekazeCTF{'
ncandi = ord('H')**e - cs[0]
for i inrange(1,len(flag_part)):
ncandi = math.gcd(ncandi,ord(flag_part[i])**e - cs[i])
print('HarekazeCTF{',end="")
for i inrange(len(flag_part),len(cs)):
for j inrange(128):
ifpow(j,e,ncandi) == cs[i]:
print(chr(j),end="")
breakprint()
from Crypto.Util.number import *
f = open("output.txt")
a = f.readlines()
flag = ""for c in a:
c = int(c.strip())
if isPrime(c): flag += "1"else: flag += "0"print(long_to_bytes(int(flag[::-1],2)))
現状、ed = 1 mod (p-1)(q-1) で秘密鍵を作っているとのことなので、ed' = 1 mod lcm(p-1,q-1) にしてd'が小さくなればいいな戦法を取ります。では、どうやってe, n, dからp, qを求めるのかというと、ed-1が(p-1)(q-1)の倍数であることを使います。
Cerberus is guarding a secret text.
nc cerberus.quals.seccon.jp 8080
ファイル：problem.py
#problem.pyimport base64
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.strxor import strxor
from flag import flag
import signal
key = get_random_bytes(16)
block_size = 16# encrypt by AES-PCBC# https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_cipher_block_chaining_(PCBC)defencrypt(m):
cipher = AES.new(key, AES.MODE_ECB) # MODE_PCBC is not FOUND :sob: :sob:
m = pad(m, 16)
m = [m[i : i + block_size] for i inrange(0, len(m), block_size)]
iv = get_random_bytes(16)
c = []
prev = iv
for m_block in m:
c.append(cipher.encrypt(strxor(m_block, prev)))
prev = strxor(c[-1], m_block)
return iv, b"".join(c)
# decrypt by AES-PCBC# https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_cipher_block_chaining_(PCBC)defdecrypt(iv, c):
cipher = AES.new(key, AES.MODE_ECB) # MODE_PCBC is not FOUND :sob: :sob:
c = [c[i : i + block_size] for i inrange(0, len(c), block_size)]
m = []
prev = iv
for c_block in c:
m.append(strxor(prev, cipher.decrypt(c_block)))
prev = strxor(m[-1], c_block)
return b"".join(m)
# The flag is padded with 16 bytes prefix# flag = padding (16 bytes) + "SECCON{..."
signal.alarm(3600)
ref_iv, ref_c = encrypt(flag)
print("I teach you a spell! repeat after me!")
print(base64.b64encode(ref_iv + ref_c).decode("utf-8"))
whileTrue:
c = base64.b64decode(input("spell:"))
iv = c[:16]
c = c[16:]
ifnot c.startswith(ref_c):
print("Grrrrrrr!!!!")
continue
m = decrypt(iv, c)
try:
unpad(m, block_size)
except:
print("little different :(")
continueprint("Great :)")
