배낭암호(Knapshot)

2018. 11. 26. 17:00

관련 개념블로그

http://ezbeat.tistory.com/332

http://jihwan4862.tistory.com/22


암호학 팀원이 쓴글

http://chieze.tistory.com/7


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

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

출제자 writeup


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

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


아래는 암복호화 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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, 01)
    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:]))
cs


+ Recent posts