祥云杯

还要再加油。

Guess

这一题是个Paillier加密方案，加解密函数都给出了 \[ c=g^mr^n\;mod\;n^2 \]

同态

Paillier加密具有同态的性质，满足:\[D(c_1c_2)=m_1+m_2\]，proof： \[ c_1=g^{m_1}r1^n\;mod \;n\\ c_2=g^{m_1}r2^n\;mod \;n\\ ∴c_1c_2=g^{m_1m_2}(r_1r_2)^n\;mod\;n\\ 即c=c_1c_2,m=m_1+m_2 \] 所以\[D(c^2)=2m\]

流程

1. 给出公钥n、g；
2. 传入一个ciphertext，给出相应的plaintext；
3. \[传入m_1和m_2，均大于2且比特位相同，随机返回E(m_1m_2KEY_R) or E(m_1m_2KEY_{R+1})\]；
4. 再传入一个ciphertext，给出相应的plaintext；
5. 猜测步骤3返回的是密文所对应的明文是哪一个；
6. 循环上述步骤32轮；

解密

传入\[m_1和m_2\]后拿到的密文记为c。在步骤5中传入\[c^2\]，则可获得加密明文的两倍。那么现在要解决的问题是key，这个利用LLL和BKZ算法能爆出来。

myRSA

加密的关键代码: \[ x=p^2(p+3q-1)+q^2(q+3p-1)\\ y=2pq+p+q\\ z\\ c=m^e\; mod\;n\\ ∴xc+yc+z=[(p+q)^3-(p-q)^2+(p+q)]c+z\\ ∵ n=pq\\ ∴上式=[(p+q)^3-(p+q)^2+(p+q)+4n]c+z\\ 令p+q=a\\ ∴cc=(a^3-a^2+a+4n)c+z \]

然后就拿到了一个线性方程，其中c的系数是1500+位的，z是1040位数，c可以自己构造，这里为了让c尽可能大所以选择m1=n-1。

现在要做的是分解n，所以两边同除c，那么右边剩下1500位+16位，测试后发现\[\sqrt{x+y}{3}=p+q-1\]，那么就得到了p+q的值，再利用\[p-q=\sqrt{(p+q)^2-4n}{2}\]就可以分解pq了。

最后\[ccc=(x+y)flag^e+z\]因为x+y的位数大于z，所以两边整除x+y即可获得flag加密后的值，最后解出flag。

import pathlib
from time import gmtime
from Crypto.Util.number import *
from pwn import *
from hashlib import sha256
import gmpy2

def dehash(s,re):
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz"
    print(s,re)
    for a in alphabet:
        for b in alphabet:
            for c in alphabet:
                for d in alphabet:
                    ss=a+b+c+d+s
                    if  sha256(ss.encode()).hexdigest()==re:
                        return a+b+c+d
def getpq(c,n):
    c1=gmpy2.iroot(c,3)[0]+1#c1=p+q
    c2=gmpy2.iroot(c1**2-4*n,2)[0]
    return (c1+c2)//2,(c1-c2)//2
    

def main():
    context.log_level="debug"
    p=remote('47.104.85.225',49877)
    p.recvuntil(b"SHA-256(?+")
    s=p.recvuntil(") == ", drop=True)
    hashre=p.recvline()[:-1]
    p.sendline(dehash(s.decode(),hashre.decode()))
    p.recvuntil(b'n = ')
    n=int(p.recvline()[:-1])
    p.recvuntil(b'e = ')
    e=int(p.recvline()[:-1])
    p.recvline()
    p.recvline()
    p.recvline()
    p.sendline(b'1')
    p.recvline()
    message=n-1
    p.sendline(long_to_bytes(message))
    p.recvline()
    cc=int(p.recvline()[:-1].decode())
    p0,q0=getpq(cc//message,n)
    assert p0*q0==n
    p.recvline()
    p.recvline()
    p.recvline()
    p.sendline(b'2')
    p.recvline()
    p.recvline()
    ccc=p.recvline()[:-1].decode()
    ccc=int(ccc)
    
    x=p0**2 * (p0 + 3*q0 - 1 ) + q0**2 * (q0 + 3*p0 - 1) 
    y=2*p0*q0 + p0 + q0
    flag=ccc//(x+y)
    phi=(p0-1)*(q0-1)
    d=gmpy2.invert(e,phi)
    print(long_to_bytes(pow(flag,d,n)))
main()

Random_RSA

题目分成两部分，前半部分是RSA的dp、c、n模式，后半部分是生成种子后生成伪随机数，再通过Feistal网络加密dp。

这一题要使用py2来解伪随机数，获取dp后在(1,e)爆破i满足\[(dp⋅e−1)%i==0(dp⋅e−1)%i==0和n%((dp⋅e−1)//i+1)==0时n%((dp⋅e−1)//i+1)==0时\]，N成功分解，证明在大佬的博客里有。

import random
import gmpy2
from Crypto.Util.number import bytes_to_long, long_to_bytes
from pwnlib import encoders

def decrypt(e, dp, n):
    _ = dp * e - 1
    for i in range(1, e):
        if not _ % i:
            p = _ // i + 1
            if not n % p:
                q = n // p
                phi = (p - 1) * (q - 1)
                d = int(gmpy2.invert(e, phi))
                return d

n=81196282992606113591233615204680597645208562279327854026981376917977843644855180528227037752692498558370026353244981467900057157997462760732019372185955846507977456657760125682125104309241802108853618468491463326268016450119817181368743376919334016359137566652069490881871670703767378496685419790016705210391
ct=61505256223993349534474550877787675500827332878941621261477860880689799960938202020614342208518869582019307850789493701589309453566095881294166336673487909221860641809622524813959284722285069755310890972255545436989082654705098907006694780949725756312169019688455553997031840488852954588581160550377081811151
e=0x10001
seeds=[4827, 9522, 552, 880, 7467, 7742, 9425, 4803, 6146, 4366, 1126, 4707, 1138, 2367, 1081, 5577, 4592, 5897, 4565, 2012, 2700, 1331, 9638, 7741, 50, 824, 8321, 7411, 6145, 1271, 7637, 5481, 8474, 2085, 2421, 590, 7733, 9427, 3278, 5361, 1284, 2280, 7001, 8573, 5494, 7431, 2765, 827, 102, 1419, 6528, 735, 5653, 109, 4158, 5877, 5975, 1527, 3027, 9776, 5263, 5211, 1293, 5976, 7759, 3268, 1893, 6546, 4684, 419, 8334, 7621, 1649, 6840, 2975, 8605, 5714, 2709, 1109, 358, 2858, 6868, 2442, 8431, 8316, 5446, 9356, 2817, 2941, 3177, 7388, 4149, 4634, 4316, 5377, 4327, 1774, 6613, 5728, 1751, 8478, 3132, 4680, 3308, 9769, 8341, 1627, 3501, 1046, 2609, 7190, 5706, 3627, 8867, 2458, 607, 642, 5436, 6355, 6326, 1481, 9887, 205, 5511, 537, 8576, 6376, 3619, 6609, 8473, 2139, 3889, 1309, 9878, 2182, 8572, 9275, 5235, 6989, 6592, 4618, 7883, 5702, 3999, 925, 2419, 7838, 3073, 488, 21, 3280, 9915, 3672, 579]

res=[55,5,183,192,103, 32, 211, 116, 102, 120, 118, 54, 120, 145, 185, 254, 77, 144, 70, 54, 193, 73, 64, 0, 79, 244, 190, 23, 215, 187, 53, 176, 27, 138, 42, 89, 158, 254, 159, 133, 78, 11, 155, 163, 145, 248, 14, 179, 23, 226, 220, 201, 5, 71, 241, 195, 75, 191, 237, 108, 141, 141, 185, 76, 7, 113, 191, 48, 135, 139, 100, 83, 212, 242, 21, 143, 255, 164, 146, 119, 173, 255, 140, 193, 173, 2, 224, 205, 68, 10, 77, 180, 24, 23, 196, 205, 108, 28, 243, 80, 140, 4, 98, 76, 217, 70, 208, 202, 78, 177, 124, 10, 168, 165, 223, 105, 157, 152, 48, 152, 51, 133, 190, 202, 136, 204, 44, 33, 58, 4, 196, 219, 71, 150, 68, 162, 175, 218, 173, 19, 201, 100, 100, 85, 201, 24, 59, 186, 46, 130, 147, 219, 22, 81]
dp=b''
#rands=[[2, 58, 53, 122], [145, 54, 124, 244], [5, 19, 128, 192], [255, 23, 64, 242], [87, 57, 113, 194], [246, 16, 205, 162], [112, 87, 228, 95], [215, 147, 105, 64], [84, 16, 131, 38], [234, 78, 36, 46], [68, 61, 71, 146], [148, 61, 9, 0], [73, 139, 77, 32], [96, 160, 56, 160], [121, 76, 128, 17], [114, 246, 92, 200], [124, 178, 206, 60], [168, 165, 147, 26], [168, 41, 114, 68], [24, 93, 84, 2], [241, 175, 43, 88], [147, 124, 97, 153], [42, 94, 118, 45], [150, 103, 127, 52], [127, 68, 163, 62], [165, 193, 37, 89], [219, 248, 142, 59], [241, 182, 8, 35], [230, 140, 211, 146], [88, 138, 226, 2], [48, 150, 5, 56], [87, 109, 255, 135], [40, 227, 216, 65], [23, 188, 190, 10], [5, 25, 28, 64], [6, 12, 124, 108], [167, 53, 113, 124], [255, 207, 192, 158], [61, 239, 166, 5], [62, 108, 86, 181], [127, 123, 44, 64], [195, 51, 192, 30], [30, 82, 168, 95], [56, 178, 165, 146], [168, 68, 77, 239], [106, 204, 247, 226], [17, 46, 62, 114], [91, 71, 156, 134], [37, 157, 43, 182], [146, 219, 6, 42], [148, 143, 234, 161], [108, 33, 139, 255], [50, 139, 169, 157], [71, 117, 140, 25], [28, 153, 194, 26], [241, 221, 235, 243], [124, 28, 131, 141], [159, 137, 111, 184], [47, 206, 221, 11], [220, 152, 157, 88], [188, 41, 213, 97], [4, 191, 220, 10], [77, 13, 143, 248], [94, 140, 110, 122], [49, 25, 250, 226], [218, 64, 102, 109], [189, 238, 143, 66], [91, 18, 131, 8], [190, 23, 239, 190], [159, 184, 33, 72], [183, 78, 85, 208], [209, 213, 101, 102], [236, 111, 50, 220], [166, 196, 104, 233], [170, 144, 34, 10], [187, 87, 175, 183], [207, 195, 59, 104], [165, 157, 179, 179], [99, 247, 160, 153], [195, 61, 100, 79], [153, 223, 159, 165], [230, 202, 93, 184], [87, 28, 184, 35], [35, 122, 38, 244], [157, 158, 188, 163], [229, 48, 192, 222], [12, 12, 211, 192], [207, 95, 224, 255], [113, 127, 113, 137], [22, 58, 114, 143], [13, 45, 117, 144], [70, 140, 211, 131], [33, 57, 101, 42], [132, 36, 62, 129], [40, 128, 246, 124], [1, 132, 161, 250], [85, 164, 33, 133], [252, 41, 201, 32], [8, 18, 203, 247], [1, 88, 55, 101], [189, 201, 135, 186], [101, 50, 254, 125], [236, 196, 81, 39], [148, 24, 103, 127], [233, 101, 29, 253], [97, 114, 156, 64], [90, 103, 233, 91], [50, 48, 80, 251], [118, 206, 22, 93], [11, 137, 114, 174], [61, 132, 76, 247], [215, 32, 232, 61], [158, 95, 128, 90], [57, 144, 35, 228], [163, 143, 233, 107], [178, 250, 28, 80], [169, 64, 107, 225], [106, 174, 115, 207], [85, 134, 1, 21], [118, 201, 76, 172], [4, 234, 34, 22], [241, 176, 236, 122], [111, 185, 137, 127], [1, 26, 164, 255], [186, 254, 57, 117], [243, 244, 27, 32], [161, 88, 28, 80], [50, 165, 93, 17], [12, 87, 182, 216], [184, 55, 159, 63], [167, 166, 246, 123], [37, 78, 33, 235], [127, 186, 81, 58], [48, 167, 3, 239], [70, 186, 114, 13], [56, 108, 178, 154], [151, 54, 55, 235], [105, 235, 180, 105], [16, 194, 155, 98], [136, 11, 41, 39], [252, 18, 203, 79], [185, 83, 114, 170], [148, 181, 87, 223], [118, 57, 160, 97], [255, 23, 250, 181], [235, 47, 219, 228], [106, 253, 14, 44], [44, 151, 38, 143], [28, 185, 224, 134], [42, 176, 162, 122], [3, 9, 164, 158], [129, 245, 2, 235], [35, 66, 241, 92], [80, 102, 124, 36]]
for i in range(len(res)):
    random.seed(seeds[i])
    rand=[]
    for j in range(4):
        rand.append(random.randint)
    dp+=chr(res[i]^rand[i%4]).encode()
dp=int(dp)
d=decrypt(e,dp,n)
print(long_to_bytes(pow(ct,d,n)))

share secret

...