MENU

Crypto LLL-Attack、python随机数

February 26, 2021 • Read: 419 • Crypto

题目 1

from Crypto.Util.number import *
import random
import os
import hashlib
from Crypto.Cipher import AES
flag = open("flag", "r").read()
logger = ""
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x10001
m = bytes_to_long(flag)
c = pow(m, e, n)
logger += str(n) + "\n"
logger += str(e) + "\n"
logger += str(c) + "\n"
random.seed(os.urandom(16))
for i in range(0x500):
    logger += str(random.getrandbits(32)) + "\n"
key = long_to_bytes(random.getrandbits(128))
m = long_to_bytes(((p >> 128) << 128))
iv = long_to_bytes(random.getrandbits(128))
h = AES.new(key, AES.MODE_CBC, iv)
c = h.encrypt(m)
logger += str(bytes_to_long(c))
open("log", "wb").write(logger)

先是随机生成两个 p 和 q,然后对 flag 进行加密。

加密后再输出 0x500 个随机数,最后再生成几个随机数用于生成 AES 的秘钥,并且对部分 p 进行加密。

这里我们先从 python 随机数入手进行攻击。Python 随机数使用 MTrand 进行生成,他的 state 是 624 个 32bit 的 word,并且 state 之间不是单纯的线性关系,而是由前 624 个生成后 624 个,利用这个我们可以进行攻击。

所以我们第一步需要根据输出的随机数来预测到接下来随机产生的秘钥,我这里使用 FlappyPig 战队的代码

https://github.com/FlappyPig/CTF_SPECIAL_TRAINING_CAMP/tree/903ec0c4f6e80603bd5768c7c79be71a49fc62a0/%E7%AC%AC%E5%9B%9B%E7%AF%87%20CTF%E4%B9%8BCrypto/hardrpd/%E8%A7%A3%E9%A2%98%E8%84%9A%E6%9C%AC

Main.java

public class Main {
    
        static int[] state;
        static int currentIndex;
    
        public static void main(String[] args) {
            state = new int[624];
            currentIndex = 0;
    
            if (args.length != 624) {
                System.err.println("must be 624 args");
                System.exit(1);
            }
            int[] arr = new int[624];
            for (int i = 0; i < args.length; i++) {
                arr[i] = Integer.parseInt(args[i]);
            }
    
            rev(arr);
    
            for (int i = 0; i < 624; i++) {
                System.out.println(state[i]);
            }
    
        }
    
        static void nextState() {
            // Iterate through the state
            for (int i = 0; i < 624; i++) {
                // y is the first bit of the current number,
                // and the last 31 bits of the next number
                int y = (state[i] & 0x80000000)
                        + (state[(i + 1) % 624] & 0x7fffffff);
                // first bitshift y by 1 to the right
                int next = y >>> 1;
                // xor it with the 397th next number
                next ^= state[(i + 397) % 624];
                // if y is odd, xor with magic number
                if ((y & 1L) == 1L) {
                    next ^= 0x9908b0df;
                }
                // now we have the result
                state[i] = next;
            }
        }
    
        static int nextNumber() {
            currentIndex++;
            int tmp = state[currentIndex];
            tmp ^= (tmp >>> 11);
            tmp ^= (tmp << 7) & 0x9d2c5680;
            tmp ^= (tmp << 15) & 0xefc60000;
            tmp ^= (tmp >>> 18);
            return tmp;
        }
    
        static void initialize(int seed) {
    
            // http://code.activestate.com/recipes/578056-mersenne-twister/
    
            // global MT
            // global bitmask_1
            // MT[0] = seed
            // for i in xrange(1,624):
            // MT[i] = ((1812433253 * MT[i-1]) ^ ((MT[i-1] >> 30) + i)) & bitmask_1
    
            // copied Python 2.7's impl (probably uint problems)
            state[0] = seed;
            for (int i = 1; i < 624; i++) {
                state[i] = ((1812433253 * state[i - 1]) ^ ((state[i - 1] >> 30) + i)) & 0xffffffff;
            }
        }
    
        static int unBitshiftRightXor(int value, int shift) {
            // we part of the value we are up to (with a width of shift bits)
            int i = 0;
            // we accumulate the result here
            int result = 0;
            // iterate until we've done the full 32 bits
            while (i * shift < 32) {
                // create a mask for this part
                int partMask = (-1 << (32 - shift)) >>> (shift * i);
                // obtain the part
                int part = value & partMask;
                // unapply the xor from the next part of the integer
                value ^= part >>> shift;
                // add the part to the result
                result |= part;
                i++;
            }
            return result;
        }
    
        static int unBitshiftLeftXor(int value, int shift, int mask) {
            // we part of the value we are up to (with a width of shift bits)
            int i = 0;
            // we accumulate the result here
            int result = 0;
            // iterate until we've done the full 32 bits
            while (i * shift < 32) {
                // create a mask for this part
                int partMask = (-1 >>> (32 - shift)) << (shift * i);
                // obtain the part
                int part = value & partMask;
                // unapply the xor from the next part of the integer
                value ^= (part << shift) & mask;
                // add the part to the result
                result |= part;
                i++;
            }
            return result;
        }
    
        static void rev(int[] nums) {
            for (int i = 0; i < 624; i++) {
    
                int value = nums[i];
                value = unBitshiftRightXor(value, 18);
                value = unBitshiftLeftXor(value, 15, 0xefc60000);
                value = unBitshiftLeftXor(value, 7, 0x9d2c5680);
                value = unBitshiftRightXor(value, 11);
    
                state[i] = value;
            }
        }
    }

libprngcrack.py

import subprocess
import random
 
def sign(iv):
    # converts a 32 bit uint to a 32 bit signed int
    if(iv&0x80000000):
        iv = -0x100000000 + iv
    return iv
def crack_prng(outputs_624_list):
    get_in=[]
    for i in outputs_624_list:
        get_in.append(sign(i))
 
    o = subprocess.check_output(["java", "Main"] + map(str, get_in))
    stateList = [int(s) % (2 ** 32) for s in o.split()]
    r = random.Random()
    state = (3, tuple(stateList + [624]), None)
    r.setstate(state)
    return r
 
'''
r=crack_prng([...])
#r.getrandbits(32)
'''
import gmpy2
import libprngcrack
from Crypto.Util.number import *
from Crypto.Cipher import AES
getlist = []
p = open("c:\\rnd.txt", "r")
for i in range(624):
    getlist.append(int(p.readline().strip()))
r = libprngcrack.crack_prng(getlist)
for i in range(0x500 - 624):
    r.getrandbits(32)
key = long_to_bytes(r.getrandbits(128))
#m = long_to_bytes(((p >> 128) << 128))
iv = long_to_bytes(r.getrandbits(128))
h = AES.new(key, AES.MODE_CBC, iv)
c = 3629097315856794876036496272387680546695207130916936447870409286660641439235258415163355492800331314008799834015606749980641030381034396816253665464536099
c = long_to_bytes(c)
m = h.decrypt(c)
p = bytes_to_long(m)
print hex(p)

因为 p = (p >> 128) << 128,所以输出的值只有 p 的部分内容

这里我们需要用到 LLL-Attack 进行计算

# partial_m.sage
 
n = 102706395226544783414112641274672591894391416216878746807754644929912445175581335470378238742923176414999927249930670447943318136441452438270356357283197464475124949153678265709581089486951962323739833002935020314236558504922905124702232920469787037902411809326441573545744566574227951257179263944516978023591
e = 65537
nbits = n.nbits()
kbits = 128
mbar = 0xe9c8803af891c25cce03526c31070143de189f70bee7c90e9efccff02ac7ec07d929ebca121d6b290455708bb39c96dd00000000000000000000000000000000
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor = n
print (mbar + x0)

计算得到的值就是 p 的全部内容,再通过 p 的值和 n 的值计算出 q 的值,最后通过 rsa 进行解密。

p = 12244220046384568355718560147957910646101667272989641924522439382568476328630595397224497779711283146202805078253820597758447533439212561744757662901813449
n = 102706395226544783414112641274672591894391416216878746807754644929912445175581335470378238742923176414999927249930670447943318136441452438270356357283197464475124949153678265709581089486951962323739833002935020314236558504922905124702232920469787037902411809326441573545744566574227951257179263944516978023591
q = n // p
e = 65537
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
c = 93408100945478830061328907675887956126872023281207326575956032471612087186555397279899170971768484640010462797726080668402736916149068712601546751482541747498853120214756313547320047445347539193945121412129928796478426041628585562327521549537944480171636486938349293156515049003124409220635221582726824193965
m = pow(c, d, n)
print(long_to_bytes(m))

题目 2(给你私钥吧)

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import base64
from flag import flag

f=open(r"D:\删我啊\pubkey.pem","r")
key=RSA.importKey(f.read())
cipher=PKCS1_OAEP.new(key)
cipher_txt=base64.b64encode(cipher.encrypt(flag))
with open(r"flag.enc","wb") as f:
f.write(cipher_txt)
f.close()

题目中给出了三个文件

flag.enc

kLNOXRLNdsu+UmM3Y+BfElLfcpGmv539ovXbFNrGMmpt5UzNo48MgnkRhPuZ1TWcNQUVS5V6ns67tG0YTYY0dV7szagoFvDTnMPOt4qOdXx5sC2j7FTVIzfYEHEujbZyN4sWsmpQBY+gn1pWYuMVQR7TBD9faxBPgAr/CiRD+0csP1bN0Kz/W73eJDlX1CpOn4nKhrMq7oJ4MGnELKrifDkfiToWTq5oNwLA4ZbqrSG4/9F/0t/ge+cAM413b2F4CRt2/Xny0CnJIOMGO5zBcM7doBvHm5Cl9Bhlr0cFtVGnjC5iG560AMoNfXy4M6G9F4X06HIocaCeUHabmHe4LQ==

privatekey.pem

-----BEGIN RSA PRIVATE KEY-----
MIIEogIBAAKCAQEA0StjnfdZqZya21dQC71jUEGqcPjnP26hWLI7mvV1kVz2jPjl
ewRbvrz3ipvKcr8OY8tuw1PWYUIEjLaetfIM3GuvbIXnfm8qqQbcWGj8sPAzDetV
B27fGyJu9Ukm3SrTyUPI6zXLjIWEjgXqhoCYihgnAbag3FSWd2DKwoE2rVs9nxz3
lSuJjPqvhjqQv9WN8Po/NYp+uLy+G/zxOHK7ufzCszCjjz/WiUZ/7yLwJ1SfU9Rg
6f67SPGuFfe/upMGlkH9U8RvyXFWD1lV2PbkGfWYGpujk3GNeF9YZZYH9RH2zEB3
g04FnzaOsFvKeWTqLcjNGxP2KinqJEo4dv9ZZwIDAQABAoIBAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAACgYEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACgYEA7k4Y
mEXMeO/vSsPoHYrvmX9zXVgztcfoSUuRdK4hG6iCMeJWfubfmQEyjgxtvF4ks0N3
R4WufojsQJyh1ykB4ypYLykSYOuYUfy7D/8ggF0AAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACgYEAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAACgYEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAACfwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=
-----END RSA PRIVATE KEY-----

pubkey.pem

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA0StjnfdZqZya21dQC71j
UEGqcPjnP26hWLI7mvV1kVz2jPjlewRbvrz3ipvKcr8OY8tuw1PWYUIEjLaetfIM
3GuvbIXnfm8qqQbcWGj8sPAzDetVB27fGyJu9Ukm3SrTyUPI6zXLjIWEjgXqhoCY
ihgnAbag3FSWd2DKwoE2rVs9nxz3lSuJjPqvhjqQv9WN8Po/NYp+uLy+G/zxOHK7
ufzCszCjjz/WiUZ/7yLwJ1SfU9Rg6f67SPGuFfe/upMGlkH9U8RvyXFWD1lV2Pbk
GfWYGpujk3GNeF9YZZYH9RH2zEB3g04FnzaOsFvKeWTqLcjNGxP2KinqJEo4dv9Z
ZwIDAQAB
-----END PUBLIC KEY-----

使用 openssl 来查看文件数据内容

openssl rsa -in privatekey.pem  -text -out private.txt

发现内容缺失,只存在 prime2 的数据,而且 prime2 的数据也只存在部分的内容

RSA Private-Key: (2048 bit, 2 primes)
modulus:
00:d1:2b:63:9d:f7:59:a9:9c:9a:db:57:50:0b:bd:
63:50:41:aa:70:f8:e7:3f:6e:a1:58:b2:3b:9a:f5:
75:91:5c:f6:8c:f8:e5:7b:04:5b:be:bc:f7:8a:9b:
ca:72:bf:0e:63:cb:6e:c3:53:d6:61:42:04:8c:b6:
9e:b5:f2:0c:dc:6b:af:6c:85:e7:7e:6f:2a:a9:06:
dc:58:68:fc:b0:f0:33:0d:eb:55:07:6e:df:1b:22:
6e:f5:49:26:dd:2a:d3:c9:43:c8:eb:35:cb:8c:85:
84:8e:05:ea:86:80:98:8a:18:27:01:b6:a0:dc:54:
96:77:60:ca:c2:81:36:ad:5b:3d:9f:1c:f7:95:2b:
89:8c:fa:af:86:3a:90:bf:d5:8d:f0:fa:3f:35:8a:
7e:b8:bc:be:1b:fc:f1:38:72:bb:b9:fc:c2:b3:30:
a3:8f:3f:d6:89:46:7f:ef:22:f0:27:54:9f:53:d4:
60:e9:fe:bb:48:f1:ae:15:f7:bf:ba:93:06:96:41:
fd:53:c4:6f:c9:71:56:0f:59:55:d8:f6:e4:19:f5:
98:1a:9b:a3:93:71:8d:78:5f:58:65:96:07:f5:11:
f6:cc:40:77:83:4e:05:9f:36:8e:b0:5b:ca:79:64:
ea:2d:c8:cd:1b:13:f6:2a:29:ea:24:4a:38:76:ff:
59:67
publicExponent: 65537 (0x10001)
privateExponent: 0
prime1: 0
prime2:
00:ee:4e:18:98:45:cc:78:ef:ef:4a:c3:e8:1d:8a:
ef:99:7f:73:5d:58:33:b5:c7:e8:49:4b:91:74:ae:
21:1b:a8:82:31:e2:56:7e:e6:df:99:01:32:8e:0c:
6d:bc:5e:24:b3:43:77:47:85:ae:7e:88:ec:40:9c:
a1:d7:29:01:e3:2a:58:2f:29:12:60:eb:98:51:fc:
bb:0f:ff:20:80:5d:00:00:00:00:00:00:00:00:00:
00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
00:00:00:00:00:00:00:00:00
exponent1: 0
exponent2: 0
coefficient: 0
-----BEGIN RSA PRIVATE KEY-----
MIIBoAIBAAKCAQEA0StjnfdZqZya21dQC71jUEGqcPjnP26hWLI7mvV1kVz2jPjl
ewRbvrz3ipvKcr8OY8tuw1PWYUIEjLaetfIM3GuvbIXnfm8qqQbcWGj8sPAzDetV
B27fGyJu9Ukm3SrTyUPI6zXLjIWEjgXqhoCYihgnAbag3FSWd2DKwoE2rVs9nxz3
lSuJjPqvhjqQv9WN8Po/NYp+uLy+G/zxOHK7ufzCszCjjz/WiUZ/7yLwJ1SfU9Rg
6f67SPGuFfe/upMGlkH9U8RvyXFWD1lV2PbkGfWYGpujk3GNeF9YZZYH9RH2zEB3
g04FnzaOsFvKeWTqLcjNGxP2KinqJEo4dv9ZZwIDAQABAgEAAgEAAoGBAO5OGJhF
zHjv70rD6B2K75l/c11YM7XH6ElLkXSuIRuogjHiVn7m35kBMo4MbbxeJLNDd0eF
rn6I7ECcodcpAeMqWC8pEmDrmFH8uw//IIBdAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAgEAAgEAAgEA
-----END RSA PRIVATE KEY-----

和之前一样,尝试使用 sage 还原内容

n = 0x00D12B639DF759A99C9ADB57500BBD635041AA70F8E73F6EA158B23B9AF575915CF68CF8E57B045BBEBCF78A9BCA72BF0E63CB6EC353D66142048CB69EB5F20CDC6BAF6C85E77E6F2AA906DC5868FCB0F0330DEB55076EDF1B226EF54926DD2AD3C943C8EB35CB8C85848E05EA8680988A182701B6A0DC54967760CAC28136AD5B3D9F1CF7952B898CFAAF863A90BFD58DF0FA3F358A7EB8BCBE1BFCF13872BBB9FCC2B330A38F3FD689467FEF22F027549F53D460E9FEBB48F1AE15F7BFBA93069641FD53C46FC971560F5955D8F6E419F5981A9BA393718D785F58659607F511F6CC4077834E059F368EB05BCA7964EA2DC8CD1B13F62A29EA244A3876FF5967
e = 65537
nbits = n.nbits()
kbits = 384
mbar = 0x00EE4E189845CC78EFEF4AC3E81D8AEF997F735D5833B5C7E8494B9174AE211BA88231E2567EE6DF9901328E0C6DBC5E24B343774785AE7E88EC409CA1D72901E32A582F291260EB9851FCBB0FFF20805D000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor = n
print (hex(mbar + x0))

由于编码方式的差异,我们直接用题目中使用的 python 模块来解密最为方便

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import base64
import gmpy2
n = 0x00D12B639DF759A99C9ADB57500BBD635041AA70F8E73F6EA158B23B9AF575915CF68CF8E57B045BBEBCF78A9BCA72BF0E63CB6EC353D66142048CB69EB5F20CDC6BAF6C85E77E6F2AA906DC5868FCB0F0330DEB55076EDF1B226EF54926DD2AD3C943C8EB35CB8C85848E05EA8680988A182701B6A0DC54967760CAC28136AD5B3D9F1CF7952B898CFAAF863A90BFD58DF0FA3F358A7EB8BCBE1BFCF13872BBB9FCC2B330A38F3FD689467FEF22F027549F53D460E9FEBB48F1AE15F7BFBA93069641FD53C46FC971560F5955D8F6E419F5981A9BA393718D785F58659607F511F6CC4077834E059F368EB05BCA7964EA2DC8CD1B13F62A29EA244A3876FF5967
p = 0x00ee4e189845cc78efef4ac3e81d8aef997f735d5833b5c7e8494b9174ae211ba88231e2567ee6df9901328e0c6dbc5e24b343774785ae7e88ec409ca1d72901e32a582f291260eb9851fcbb0fff20805dfd7c56f39028926fb8cf1fe3d7888cf7f9ca3387032ffe8a53925e79c3c464476ec1ebad7f14ed73d1646f6fca9a3207
q = n // p
e = 65537
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
u = gmpy2.invert(p, q)
key = RSA.RsaKey(n=n, e=e, d=d, p=p, q=q, u=u)
cipher = PKCS1_OAEP.new(key)
data = base64.b64decode( "kLNOXRLNdsu+UmM3Y+BfElLfcpGmv539ovXbFNrGMmpt5UzNo48MgnkRhPuZ1TWcNQUVS5V6ns67tG0YTYY0dV7szagoFvDTnMPOt4qOdXx5sC2j7FTVIzfYEHEujbZyN4sWsmpQBY+gn1pWYuMVQR7TBD9faxBPgAr/CiRD+0csP1bN0Kz/W73eJDlX1CpOn4nKhrMq7oJ4MGnELKrifDkfiToWTq5oNwLA4ZbqrSG4/9F/0t/ge+cAM413b2F4CRt2/Xny0CnJIOMGO5zBcM7doBvHm5Cl9Bhlr0cFtVGnjC5iG560AMoNfXy4M6G9F4X06HIocaCeUHabmHe4LQ==")
flag = cipher.decrypt(data)
print(flag)
#b"bugku{1T's_a_fake_prikey@qaq}"

这里在填参数的时候还学习一下对应参数的意义
内容来自于代码注释(其中我不认识的是u为p和q的逆元

名称意义
nThe modulus.
eThe public exponent.
dThe private exponent. Only required for private keys.
pThe first factor of the modulus. Only required for private keys.
qThe second factor of the modulus. Only required for private keys.
uThe CRT coefficient (inverse of p modulo q). Only required for
private keys.
Archives QR Code Tip
QR Code for this page
Tipping QR Code