배낭암호(Knapshot)

관련 개념블로그

http://ezbeat.tistory.com/332

http://jihwan4862.tistory.com/22

암호학 팀원이 쓴글

http://chieze.tistory.com/7

격자줄이기는 다음에 차차..

관련 문제로는 H3XOR CTF의 Cryingbag문제가 있다. 

출제자 writeup

대부분이 Bruteforcing으로 풀었다고 하더라... 심지어 출제자도... 참고로 필자는 (역연산+알려진 플래그앞부분)으로 풀었었다.

역연산이 됬다는게 신기..

아래는 암복호화 소스

import random
from binascii import hexlify, unhexlify
from fractions import gcd
 
def genRandomSINumber(arr):
    s=sum(arr)
    return random.randrange(s+1,(s+1)<<2)
 
def genCoprime(n):
    x=n
    while gcd(n,x)!=1:
        x=random.randrange(n>>1+1,n)
    return x
 
def keyGenerate(bits=1024):
    if bits%4!=0:
        raise Exception("Weird bits")
    w = []
    for i in range(bits):
        w.append(genRandomSINumber(w))
 
    q = genRandomSINumber(w)
    r = genCoprime(q)
    pubkey = [(r * i) % q for i in w]
    privkey = (w, q, r)
    return pubkey,privkey
 
def encrypt(pubkey,msg):
    msgbits = bin(msg)[2:]
    if len(pubkey)<len(msgbits):
        raise Exception("Msg is too big")
    plainbits=['0']*(4-len(msgbits)%4)
    plainbits+=msgbits
    c=0
    for a,b in zip(map(int,plainbits),pubkey):
        c+=a*b
    return c
 
def 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)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m    
    
def decrypt(privkey,enc):
    w = privkey[0]
    q = privkey[1]
    r = privkey[2]
    
    g = modinv(r,q)
    
    plainbag = (enc*g)%q
    plainbits = ""
 
    for i in range(len(w)-1, -1, -1):
        if plainbag-w[i] >= 0:
            plainbag-=w[i]
            plainbits += "1"
        else:
            plainbits += "0"
    return int(plainbits[::-1],2)
    
if __name__ == '__main__':
    msg=input("Your Message : ")
    msg=int(hexlify(msg.encode()),16)
    bits=len(bin(msg))-2
    bits+=(4-bits%4)
 
    p,q=keyGenerate(bits)
    c=encrypt(p,msg)
    
    msg = decrypt(q,c)
    print(unhexlify(hex(msg)[2:]))