天翼杯Crypto Write Up

 

上周五参加了天翼杯，其中的密码学赛题整体难度中等左右，这里记录下全部四道赛题的题解。

Easy RSA

题目代码:

from Crypto.Util.number import *
from gmpy2 import invert
from secret import flag,e

def enc(key, p):
    e, n = key
    cipher = [pow(ord(char), e, n) for char in p]
    return cipher

def dec(pk, c):
    key, n = pk
    plain = [chr(pow(char, key, n)) for char in c]
    return ''.join(plain)

p = getPrime(512)
q = getPrime(512)
n = p*q
pubkey = (e,n)
assert(e < 20000)
print("Public key:")
print(pubkey[1])

cipher = (enc(pubkey, flag))

print("Encrypted flag:")
print(cipher)

这题的enc函数中，将flag的每个字节分别进行加密，这导致明文空间只有256,简单枚举即可算出m。

虽然e还不知道，但是我们知道flag是以flag{开头的，利用’f’和对应的密文，在(1,20000)范围内爆破，即可得到e

exp如下：

from gmpy2 import *
n = 53868412634233045090369153437747412878975425992040754576346754596620347350784422917543759897936684646663150893442998869763798006729979997564587680875175995309635877031073898192380128134509976889005408768734374216063639902277690308505919178272615191163114645916867249827856751349851814346547505622471483949937
f = open('output' , 'r')
c = f.readline()[:-1]
c = [int(i) for i in c.split('L, ')]

for i in range(20000):
    if pow(ord('f') , i , n) == c[0]:
        e = i
        break

flag = ''
for cipher in c:
    for i in range(256):
        if pow(i , e , n) == cipher:
            flag += chr(i)
            break
print(flag)

 

AliceHomework

题目所用的密码系统为knaspack，给了公钥为303维，直接规约以后并不能得到理想的向量。

因此我采用了一点小小的技巧来降维。

由于flag的格式为flag{32位16进制数}

flag{}这里6个字节我们是已知的，因此可以去掉48维。

稍加观察还可以发现，16进制的数他们的ascii码的2进制，满足0#1#####。

因此对于每一位都还可以去掉2维。这里可以去掉64维。

所以最后只剩下了192维，LLL规约后，即可得到解向量

exp:(sage)

from Crypto.Util.number import *
def backpacker(n  , c , K):
    M = matrix(ZZ , n+1 , n+1)
    N = 2 ^ 333
    for i in range(n):
        M[i,i] = 2
        M[n,i] = 1
        M[i,n] = K[i] * N
    M[n,n] = c*N
    tmp = M.BKZ(blocksize = 22)[0]
    if tmp[-1] != 0:
        print('wrong')
        return 0
    else:
        print(tmp)
c = 48900138654057608906330336094404001410012416314129947343718254788658710361958972300167501443635234828803130486373878734082851314709567051747373094122800043398642622361749518265923115930476719470463043632323571459743381102290686602475870167398059452505895370462341540956691006903515181773586159733875651
f = open('./output' , 'r')
key = f.readline()[:-1]
key = [int(i) for i in key.split('L, ')]
plain = bin(bytes_to_long(b'flag{'))[2:]
for i in plain:
    if i == '1':
        c -= key[0]
    key = key[1:]
true_key = []
for i in range(32):
    choose_list = [1,3,4,5,6,7]
    for j in choose_list:
        true_key.append(key[i * 8 + j])
    c -= key[i * 8 + 2]
plain = bin(ord('}'))[2:].rjust(8 , '0')
key = key[-8:]
for i in range(8):
    if plain[i] == '1':
        c -= key[i]
print(len(true_key))

alist = backpacker(len(true_key) ,c ,true_key)
flag = ''
for i in range(32):
    tmp = 2**5
    valuelist = [64,16,8,4,2,1]
    for j in range(6):
        if alist[i*6 + j] == -1:
            tmp += valuelist[j]
    flag += chr(tmp)
print(flag)

 

hard rsa

题目代码：

from Crypto.Util.number import *
from gmpy2 import invert
import os
from secret import flag
p = getPrime(510)
q = getPrime(510)
r = getPrime(510)
e = 7
m = bytes_to_long(os.urandom(30)+flag)
n = p*q*r
d = invert(e,(p-1)*(q-1)*(r-1))
c = pow(m,e,n)
print n/p
print p
print c
print hex(d%(1<<540))

代码很短，三元rsa，泄露了d的低位。所以可以用coppersmith的partical d的思路来写。

但是因为这里，q和r都为510位，而d给了低540位，因此可以不用转化为partical p（因为已经可以直接算出p了）

具体思路如下：

因此，左边右边与模同时除以公因数即可。又因为已知这里的p-1中2的次数为4【p-1 = 2^4 * 某个奇数】,k中2的次数最多为2（当k= 4时）, 因此模最小为2^540 / 2^6 = 2^ 534，又q+r为511位，因此直接求逆即可得到q+r，接下来解一元二次方程即可分解n

exp:

from gmpy2 import *
from Crypto.Util.number import *
def Solve(a , b , c):
    '''solve ax^2+bx+c=0 , return x1 , x2'''
    delta = b**2 - 4 * a * c
    if delta < 0:
        return 0
    if is_square(delta):
        sqr_delta = isqrt(delta)
        temp1 = -b + sqr_delta
        temp2 = -b - sqr_delta
        if temp1 % (2*a) != 0 or temp2 % (2*a) != 0:
            return 0
        else:
            return [temp1//(2*a) , temp2//(2*a)]
    else:
        return 0
n = 4049584030002970545664080823848129582938411034556792600914380229461546791772327894437844974694562804322320098597200821632361860404029749610290918822378230751309535193434791281064861182569710224863795884931806318447090299326829551214573212997789976022379378237846483710647686355658059931581771863291348036943
p = 3141886348112988339174865432179206412942588390228169645162293920470188882447855208783220899752887620221059861467348059334030873350571979462363834615231089
c = 8696771272015513736887843395612361647314297287781507609196936354183211655364744684164300710583625473872942712063309507651496314800393009480421886926137403759228421858414833429980059903049311837014449093365911603108158352871851677457256058510822509157407703210866317472894586087554001158540951787167699161720491198674848526093644131709561995379565643716017359731201935855247285498574923656191121426618306186331615280461405913653781283860760013215603007314688132
d0 = 0x414946b9c40728f9801e61e98ec6d17525cbe4163a5ffb8367b65c652ae4cc3abce62e70afbfb84fcf937b3119953b48922be19ef4312c4f3a88313368ca6c9b1d658b7
e = 7
for k in range(1 , 7):
    module = 2 ** 539
    right = k * (p - 1) * (n+1) + 1 - e * d0
    left = k * (p-1)
    while 1:
        if left % 2 == 0:
            left //=2 
            right //= 2
            module //= 2
        else:
            break
    s = (invert(left , module) * right) % module
    if isinstance(Solve(1 , -s , n) , list):
        q , r = Solve(1 , -s , n)
        break
print(q)
print(q *r == n)
phi = (p-1)*(q-1)*(r-1)
d = invert(e , phi)
print(long_to_bytes(pow(c ,d , n * p)))

 

Polycrypto

题目实现了一个多项式的ntru加密，并且给了私钥。只需要写一个解密函数即可。

首先了解一下在这个多项式环(PolynomialRing(Integers(q)))上的运算。

很简单，加法乘法都与正常乘相同，不过任何一项的系数大于q时，都要模q取余数；

取的素多项式为x^N -1​，当出现N次以上的项的时候，得先模这个素多项式。使用的这个多项式，效果可以看作将次数大于或等于61的项除以x^61

（比如4x^62会变成4x）

接下来看一下它的加密过程。

另外，还有一点要注意的，原题中，给的任何数据，都是模q的最小非负剩余。可在生成g，m和r的时候，有用到-1,这就导致，模q以后，它会变成q-1.而如果在上面模q的几步中，使用最小非负剩余，那么mf极有可能有系数大于q，导致转换模的前提条件失效。因此，需采用绝对最小剩余（即系数在-q/2到q/2之间）才能成功解密。

exp:(本题可以用python写，但懒，用sage)

from Crypto.Util.number import long_to_bytes
Zx.<x> = ZZ[]
n = 61
q = 5039
p = 11

def mul(f,g):
    return (f * g) % (x^n-1)

def bal_mod(f,q):
    g = list(((int(f[i]) + q//2) % q) - q//2 for i in range(n))
    return Zx(g)
def inv_mod_prime(f,p):
    T = Zx.change_ring(Integers(p)).quotient(x^n-1)
    return Zx(lift(1 / T(f)))
def decrypt(c,key):
    f,f3 = key
    a = bal_mod(mul(c,f),q)
    a = bal_mod(a , p)
    return bal_mod(mul(a,f3),p)


if __name__ == "__main__":
    c = [[221, 4761, 791, 4565, 163, 2959, 2174, 2402, 3083, 4464, 340, 752, 4898, 709, 3085, 4393, 156, 3680, 600, 2074, 3058, 4331, 1621, 2977, 2420, 891, 429, 4304, 3811, 2672, 3615, 3592, 1069, 561, 3183, 1197, 931, 1625, 89, 4118, 1214, 2147, 3542, 3305, 1192, 2768, 4519, 2672, 1548, 2598, 4075, 1667, 577, 924, 810, 1239, 4033, 2198, 2742, 4197, 2069], [1249, 2762, 483, 3324, 449, 1647, 1024, 3292, 285, 83, 1144, 1818, 2323, 2215, 1157, 2370, 3735, 1712, 3278, 1118, 3073, 4803, 783, 4765, 3120, 4709, 3304, 199, 987, 4939, 3969, 1749, 1045, 450, 40, 1644, 1143, 2642, 1464, 3462, 1990, 1235, 4756, 2240, 2808, 4728, 3874, 3746, 2106, 926, 778, 1071, 3488, 3469, 926, 4497, 2220, 1425, 4549, 3130, 4937], [4287, 3659, 4672, 521, 3387, 1631, 674, 1739, 1927, 1655, 4653, 4772, 245, 216, 845, 3161, 2756, 1752, 2562, 2893, 443, 1195, 2430, 2438, 152, 4567, 965, 1200, 1709, 1109, 3349, 2988, 147, 3214, 4391, 2726, 1531, 251, 2685, 1624, 2963, 2385, 4992, 4995, 3296, 3262, 4337, 1002, 63, 959, 2631, 315, 4114, 1292, 3588, 1867, 3349, 3928, 3886, 1258, 2783], [834, 3120, 1420, 3534, 3926, 2862, 1840, 1083, 3258, 3146, 1080, 145, 119, 3348, 4115, 1551, 3426, 2077, 3493, 4002, 3008, 1321, 2182, 4197, 3047, 3349, 1555, 709, 2803, 63, 2792, 538, 4943, 1081, 2204, 2993, 4398, 1007, 3623, 4243, 2276, 2332, 2287, 363, 3920, 2229, 3078, 1438, 1152, 297, 3425, 4381, 3651, 3818, 2970, 159, 3726, 1190, 1645, 632, 2697]]
    f = [12, 0, 5028, 0, 11, 0, 5028, 11, 5028, 11, 11, 5028, 0, 5028, 11, 0, 0, 0, 0, 5028, 5028, 0, 5028, 11, 0, 0, 0, 11, 0, 5028, 0, 0, 5028, 0, 11, 0, 5028, 5028, 0, 0, 0, 11, 0, 11, 0, 0, 5028, 0, 11, 5028, 0, 0, 0, 11, 0, 5028, 11, 0, 0, 5028, 5028]
    f = bal_mod(Zx(f) , q)
    f_p = inv_mod_prime(f , p)
    flag = b''
    for i in range(len(c)):
        tmp = list(decrypt(Zx(c[i]),(f , f_p)))
        print(tmp)
        res = 0
        for j in range(len(tmp)):
            res += (tmp[j]+1) * (3 ^ j)
        flag += long_to_bytes(res)
    print(flag)