Encoding Challenge

from pwn import * # pip install pwntools
import json
import base64
import codecs

r = remote('socket.cryptohack.org', 13377)

def json_recv():
    line = r.recvline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)
   
def decoding(types, received):
    if(types == "base64"):
        answer = base64.b64decode(received).decode()
        return answer
    if(types == "hex"):
        answer = str(bytes.fromhex(received))
        return answer[2:len(answer)-1]
    if(types == "rot13"):
        answer = codecs.encode(received, 'rot_13')
        return answer
    if(types == "bigint"):
        answer = str(bytes.fromhex(received[2:]))
        return answer[2:len(answer)-1]
    if(types == "utf-8"):
        answer = ""
        for i in received:
            answer += chr(i)
        return answer

while (True):
    received = json_recv()
    print("Received type: ", end="")
    print(received["type"])
    print("Received encoded value: ", end="")
    print(received["encoded"])

    answer = decoding(received["type"], received["encoded"])

    print("answer: ", end="")
    print(answer)

    to_send = {"decoded": answer}
    request = json.dumps(to_send).encode()
    r.sendline(request)
    
    print("OK")

favorite byte

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

tmp="73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d"

orded = [i for i in bytes.fromhex(tmp)]

for i in range(0xff):
    ans = ""
    for j in orded:
        ans += chr(i^j)
    print(ans)

print(orded)

Privacy-Enhaced Mail

from Crypto.PublicKey import RSA


pubkey = RSA.importKey(open('privacy_enhanced_mail_1f696c053d76a78c2c531bb013a92d4a.pem').read())
e=pubkey.e
n=pubkey.n
d=pubkey.d

print("e:", e)
print("n:", n)
print("d:", d)

CERTainly not

openssl x509 -in 2048b-rsa-example-cert_3220bd92e30015fe4fbeb84a755e7ca5.der -out tmp.pem -outform pem  

SSH key

from Crypto.PublicKey import RSA


pubkey = RSA.importKey(open('bruce_rsa_6e7ecd53b443a97013397b1a1ea30e14.pub').read())
e=pubkey.e
n=pubkey.n
#d=pubkey.d

print("e:", e)
print("n:", n)
#print("d:", d)

Quadratic Residues

from Crypto.Util.number import *

p = 29
ints = [14, 6, 11]

for i in ints:
  for j in range(29):
    if(pow(j,2,p) == i):
      print(i, j)

Legendre Symbol

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139

ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]

a = 0
for i in ints:
    if pow(i,(p-1)//2,p) == 1:
        a = i
        break

print(pow(a,(p+1)//4,p))

Modular Square Root

def legendre(a, p):
    return pow(a, (p - 1) // 2, p)

def tonelli_shanks(a, p):
    if legendre(a, p) != 1:
        raise Exception("not a square (mod p)")
    # Step 1. By factoring out powers of 2, find q and s such that p - 1 = q 2^s with Q odd
    q = p - 1
    s = 0
    while q % 2 == 0:
        q >>= 1
        s += 1
    # Step 2. Search for a z in Z/pZ which is a quadratic non-residue
    for z in range(2, p):
        if legendre(z, p) == p - 1:
            break
    # Step 3.
    m = s
    c = pow(z, q, p) # quadratic non residue
    t = pow(a, q, p) # quadratic residue
    r = pow(a, (q + 1) // 2, p)
    # Step 4.
    t2 = 0
    while True:
        if t == 0: return 0
        if t == 1: return r
        t2 = (t * t) % p
        for i in range(1, m):
            if t2 % p == 1:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        m = i
        c = (b * b) % p
        t = (t * c) % p
        r = (r * b) % p


a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

print(tonelli_shanks(a, p))

Adrien’s Signs

平方剰余が何だったかというと,mod N で平方根が存在するかどうか,という話. つまり以下のようになる.

1^2 = 1 mod 7
2^2 = 4 mod 7
3^3 = 2 mod 7

みたいな感じで,この場合は 1, 2, 4 が平方剰余ということができる. で,例えば a が法 p において平方剰余かどうかを示す記号があって,これをルジャンドル記号と呼ぶんだった.

(a/p) = 1 なら, a は法 p において平方剰余. これは,(a/p) = a^((p-1)/2) みたいな感じで求めることができる. (a/p) はただの記号であることに気を付ける.

で,今回の問題では p = 1007621497415251 = 3 mod 4 . このとき,bit が 1 or 0 で与えられる n の正負が決まるので, (a/p) が分かれば 1, 0 が分かる(負数に平方剰余はない)

from Crypto.Util.number import long_to_bytes

a = 288260533169915
p = 1007621497415251

out = [snip]

res=[]

for i in out:
    if pow(i, (p-1)//2, p)==1:
        res.append('1')
    else:
        res.append('0')

print(long_to_bytes(int(''.join(res), base=2)).decode())

Modular Binomials

N = p*q
c1 = (2*p + 3*q)**e1 mod N
c2 = (5*p + 7*q)**e2 mod N

p, q 以外が与えられていて p, q を求める.

from random import randint
from Crypto.Util.number import long_to_bytes
import math

N = snip

p = math.gcd(pow(b2,(-e2 * e1),N) * pow(c2, e1, N) - pow(b1, (-e1 * e2), N) * pow(c1, e2, N), N)
q = math.gcd(pow(a2,(-e2 * e1),N) * pow(c2, e1, N) - pow(a1, (-e1 * e2), N) * pow(c1, e2, N), N)

print(p, q)