crypto.py

import hashlib

PRIME = 10162817389166932304743927803664677577393035849460315554227038992256439669168822924924642681859165915398841119695331997622323074382673543580118593098794075768017359068156207668418577358758037040886636583057751950491466568754968161402970164774854422196808968101372380404300325099055524339557705423721707
G = 1323857230486534278

def get_salt(m):
	for _ in range(1000):
		m = hashlib.sha512(m).hexdigest()
	return m

FLAG = open('flag.txt').read()
SALT = get_salt(FLAG)

def make_certificate(user, passwd):
	g = 1
	certificate = 0
	for i in SALT + user + passwd:
		certificate = (certificate * certificate + ord(i) * g) % PRIME
		g = g * G % PRIME

	return pow(certificate,2**len(SALT + user + passwd),PRIME)

users = {
	"test" : "test" ,
	"hoge" : "fuga" ,
	"tdf" : "ctf",
	"username" : "password",
	"flag" : "uasqlpgeqezahcqokjgelksxvqosmrhekbycrzpcmmmcmqbbve",
}

def check(user, passwd, certificate):
	if user not in users or users[user] != passwd:
		return 'incorrect user or passwd'
	if make_certificate(user, passwd) != certificate:
		return 'invalied certificate'

	if user != "flag":
		return 'correct certificate :)'
	else:
		return 'flag is %s' % FLAG


user = raw_input('Username? =>\n')
password = raw_input('Password? =>\n')
cert = int(raw_input('Certificate? =>\n'))

print(check(user, password, cert))

# assert make_certificate("username","password") == 4029302339347792742988803829605698219359553252266609194051324225409838632876973751246996003281440406896707077380405396496115576341669768749038756501471554229868033487448283707824769785180576772541971192206586875756981909976281605239437292768931937729639812395188200405751755825424848357613356524084583
# assert make_certificate("test","test") == 3229702347162577280595819244146852282836064570165061483993584466748279869970953942230432805290834973779054005836845235611759220528641516494944747542542533026928240447551207174799797264641323891156688046013674068773884777175272821880850251611669225391892545313605312401953793306429611969320928697745634
# assert make_certificate("test","te") == 7686904326912379328493741589962807414136794934311933172962482402578421684293004550992254322284281608133739817787939208036162181512022155614489756234246709095859972792955880206243591354118028908195331302275356406175573015955021437560965055766612469829271481544499305970250381047119303215742180258660192
# assert make_certificate("st","") == 7863272001932407091346456145335755926953363544503810867544270617302981706071795597120319752375478972327781210420047381175963653026374846009462305830822535703558245488257059841368198534800024895151566378773068015243954066302243748867214926508189599001938657685847174868078712268055901281014522218811295
# assert make_certificate("tdu","ctf") == 7417993921652447321188221244020966340148743898321002261852641468853194633663468886051961992833315104336305357721653760855276650027807178349804132655529525740710692834588717846701113855522463929124191095076622510940677840740715295910984657759338255464809938734644475406307893296992838094966468975165153
# assert make_certificate("flag","hoge") == 517906897684644312376625946470650126580559701993662218580134832498818952877731987006610432089564241134307089944783779003879373054369587580789957253360344583776721840330199366196130138232435336054043210571671604991855744422848295991342166017292399492852383633264768736081183061222301777466185387031289
# assert make_certificate("flag","fuga") == 8678097412920493129239198683427083691834567253158856410448793617970379405010505185876984249541223295192558577738867509413557956784544915313928966520722768913670938946577888579902143260756061733405148036125695061890746068947384542666623201202602223840824603210794550630668044769821800687772977208067095
# assert make_certificate("flag","wasureta") == 718132527366803322552793454524020930864075137213256773806164868939593073194471943625383616872135046772113054315958983741359052488806463893859906521470679892026496931385712844526806815162378621737408023118330109328128838679250531088232405491666354739035979113063764696145742063333420416158035348792148

flag.txt

TDU{Tonelli_Shanks_algorithm_is_awesome!}

solve.md

ポイント

証明書計算は2つの部分に分ける事が出来る．

前半

g = 1
certificate = 0
for i in SALT + user + passwd:
    certificate = (certificate * certificate + ord(i) * g) % PRIME
    g = g * G % PRIME

後半

return pow(certificate,2**len(SALT + user + passwd),PRIME)

前半を pre_make_certificate,後半を post_make_certificate と定義する．つまり

def pre_make_certificate(user,passwd)
    g = 1
    certificate = 0
    for i in SALT + user + passwd:
        certificate = (certificate * certificate + ord(i) * g) % PRIME
        g = g * G % PRIME

def post_make_certificate(user,passwd,certificate):
    return pow(certificate,2**len(SALT + user + passwd),PRIME)

def make_certificate(user,passwd):
    pre_certificate = pre_make_certificate(user,passwd):
    return post_make_certificate(user, passwd, pre_certificate)

pre_make_certificate("","") の結果がわかれば，任意のpre_make_certficate(user,passwd) が計算出来る事がわかる． 具体的には

def pre_make_certficate2(user,passwd):
    g = pow(G,len(SALT),PRIME)
    certificate = pre_make_certificate("","")
    for i in user + passwd:
        certificate = (certificate * certificate + ord(i) * g) % PRIME
        g = g * G % PRIME
    return certificate

と計算出来る

どの様に計算すれば？

• Tonelli-Shanks algorithm a^2 = x (mod p) を高速に求める事が出来るアルゴリズム これを知っていれば貼り付けるだけだが…

• 平方剰余の相互法則 "平方数 mod" でググると出てくる a^2 = x (mod p)の，解a が存在するかを判定する方法 x^((p-1)/2) == 1 なら解 a は存在， -1 なら存在しない

• 式変形を頑張る a^2 = x (mod p) なる a が存在する場合のみ考える． x^((p-1)/2) == 1 より a^2 * 1 = x * x^((p-1)/2) (mod p) a^2 = x^((p+1) / 2) (mod p) 今回，p % 4 == 3 なので， (p+1) / 4 は整数． x^((p+1) / 4) の 2乗 は x ^ ((p+1) / 2) なので，これは解の１つとなる．

  ところで，a^2 = x の解は高々2個である．一方の解を b とすると，もう一方は -b となる． (b^2 = x の時， (-b)^2 = x となるため) 3個以上存在しないことは，背理法で示せば良い

以上で， a^2 = x (mod p) が求められた． しかし，今回求めたいのは a^(2^length) == certificate である． 上記のアルゴリズムを length 回実行すれば解は求められるが，解の個数は 1, 2, 4, 8, 16, ... と増加して，計算出来ない可能性が… と感じるが，実は何回反復しても，回は高々2個になる．

というか拡張gcdで (a^(2^length)) ^ y = certificate ^ y a^2 = certificate ^ y となるのでこっちでもいい

• p % 4 == 3 の時，aの平方剰余が 1 ならば，-a の平方剰余は必ず -1 となる 証明は省略する．

上の二つを組み合わせると， a^(2**k) = x (mod p) から a を高速に求める事が出来る len(SALT)は固定なので，これが計算出来れば pre_make_certificate("","") の候補が 2個 となる．

この2つの候補を，手元で他の(user,passwd,certificate) の組と一致するか確かめれば，pre_make_certificate("","")を特定することが出来る．

後は

def answer():
  pre = pre_make_certficate2('flag','uasqlpgeqezahcqokjgelksxvqosmrhekbycrzpcmmmcmqbbve')
  return pow(pre,len('flag') + len('uasqlpgeqezahcqokjgelksxvqosmrhekbycrzpcmmmcmqbbve') + SALT_length,PRIME)

を計算すればよい．