虎符crypto_GM



  • GM加密

    勒让德符号
    134bfd91-51f6-4459-b334-be71b4df7671-image.png
    雅可比符号
    ac5bf285-d89c-43a4-adaa-138a1ba686a7-image.png

    具体过程:
    密钥产生:
    1. 大素数p,q,求出N=p*q
    2. 任取R,满足
    179133a4-8b69-4e41-b5c8-5e8002cce67b-image.png(J()雅可比符号)
    3. PK(R ,N),SK (p,q)

    加密:
    1. B将明文转化为二进制数字M=(m1,m2,m3… mk) ∈{0,1}
    2. 对于每一个mi,都对应选取一个xi ∈{1,N-1}
    若mi=1 ci= R*xi^2 mod N
    若mi=0 ci=xi^2 mod N
    3. C ={c1,c2,c3…ck} 将这个C发给A

    解密:
    对于每一个ci 都求J(ci/p)与J(ci/q) ,
    若J(ci/p)与J(ci/q)都=1,mi=0 ,若J(ci/p)与J(ci/q)都=-1,mi=1
    最终得到密文

    虎符2020_crypto_GM

    题目:

    from secret import flag
    import random
    from Crypto.Util.number import *
    from fractions import gcd
    
    def make_key( nbit):
        while True:
            p, q = getPrime(nbit), getPrime(nbit)
            N, phi = p * q, (p-1)*(q-1)
            x = random.randint(1, N)
            if (N % 8 == 1) and (phi % 8 == 4) and (p != q):
                if pow(q ** 2 * x, (p-1)/2, p) + pow(p ** 2 * x, (q-1)/2, q) == N - phi - 1:
                    break
         
        return (x, N), phi
    
    def encrypt(msg, pkey):
        msg, cipher = bin(bytes_to_long(msg))[2:], []
        x, N = pkey
        for bi in msg:
            while True:
                r = random.randint(1, N)
                if gcd(r, N) == 1:
                    br = bin(r)[2:]
                    c = (pow(x, int(br + bi, 2), N) * r ** 2) % N
                    cipher.append(c)
                    break
        return cipher
    nbit = 1024
    
    pkey,phi = make_key( nbit)
    enc = encrypt(flag, pkey)
    print phi
    print pkey[1]
    print enc
    

    输出文本为 phi,N和335个密文
    题目类似 https://ctftime.org/writeup/16120的题,且更加简单。
    明文的每一位均被独立加密,零位被编码为平方模N = pq,另一些被编码为非平方模N,这样雅各比符号仍为+1。知道N的素数分解后,就可以通过计算编码值模p的勒让德符号来解密每个位(+1表示零,-1表示1)。

    脚本用到sagemath,相关链接https://www.lainme.com/doku.php/blog/2009/12/sage%E7%9A%84%E5%AE%89%E8%A3%85

    通过pq = N和p + q = N-phi + 1; 求解二次方程

    n=...
    phi=...
    p=(n-phi+1-((n-phi+1)^2-4*n).nth_root(2))//2
    q=n//p
    print p
    

    计算编码值模p的勒让德符号来解密每个位

    Fp=Integers(p) 
    flag=[...]
    f2=[0 if Fp(f).is_square() else 1 for f in flag] hex(int('0'+''.join(str(i) for i in f2),2))[2:-1].decode('hex')
    

    结果:
    4e8840b8-f4ed-4696-9f79-0ed86f1eaa97-image.png


Log in to reply