2019年强网杯crypto部分题解

作者: liwl23 | 来源:发表于2019-05-28 00:30 被阅读0次

一、random study

这个题目中共给出了三个challenge。

1. challenge 1

服务器将python中的random模块的种子设置为int(time())，然后生成随机数让我们猜，只要我们猜对一次就可以通关了。
题目中给了200次机会，应该是考虑到服务器与我们机器的时间不同步的问题（可能相差几秒）。我这里假定服务器时间与本地时间相差不超过10秒，然后对这20种情况进行枚举就好了。相应代码如下：

2.challenge 2

服务器自己调用了一个Java程序生成了三个随机数，然后将前两个告诉我们，让我们猜第三个。
用Java Decompiler对提供的Java程序进行反编译得到源码如下：

public class Main {
  public static void main(String[] paramArrayOfString) {
    Random random = new Random();
    System.out.println(random.nextInt());
    System.out.println(random.nextInt());
    System.out.println(random.nextInt());
  }
}

可以看出这个Java程序是使用了Random类的nextInt函数来生成随机数的。百度一下这个类，可以查到官方文档。从官方文档中可以知道：

Random的nextInt函数就是直接调用next(32)并将得到的值返回。
next(int n)会通过以下方式更新内部存储的seed值，并返回下一个随机数。

//seed乘一个数，然后取低48位。
seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
// 48位种子的前n位。
return seed>>(48-n);

setSeed(long n)会将n做一些变化，然后存储到内部的seed中。

seed = (n^ 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);

根据以上知识，我们可以发现，如果我们用nextInt获得了一个随机数 $n$ ，那么生成这个随机数时的种子就是 $n*2^{32}+x$ ，其中x是一个16位的整数。
因此我们根据题目中给出的第一个随机数可以推断出生成第二个随机数的种子的前32位，然后我们通过对低16位进行枚举就可以得到生成第二个随机数的种子是多少了。

3. challenge3

这一题就没什么了，只要challenge1通过了，这里直接调函数得到随机数，然后发过去就好了。

代码如下:

from pwn import *
import time
from aux import *
import tqdm
import random
import subprocess

conn = remote('119.3.245.36', 23456)

def solveChaleneg1(conn):
    conn.recvuntil('[-]')
    cur_time = int(time.time())
    for i,j in (enumerate(range(cur_time-10,cur_time+10)),initial=0,total=20):
        random.seed(j)
        for k in range(i):
            random.randint(0,2**64)
        conn.sendline(str(random.randint(0,2**64)))
        if 'fail' not in conn.recvline():
            break

def solveChalenge2():
    conn.recvuntil('[-]')
    x1 = conn.recvline()
    print x1
    x1 = int(x1)
    print(x1)
    conn.recvuntil('[-]')
    x2 = int(conn.recvline(),10)

    o = subprocess.check_output(["java", "MyMain",str(x1),str(x2)])
    x3 = int(o.split('\n')[0],10)
    print "x1=%d,x2=%d,x3=%d"%(x1,x2,x3)
    conn.recvuntil('[-]')
    conn.sendline(str(x3))
    if 'fail' in conn.recvline()[:-1]:
        print "challenge2 fails"


def solveChalenge3():
    target = random.getrandbits(32)
    conn.recvuntil('[-]')
    conn.sendline(str(target))
    conn.recvuntil("[++++++++++++++++]challenge 3 completed[++++++++++++++++]")
solveSHA(conn)
solveChaleneg1(conn)
solveChalenge2()
solveChalenge3()
conn.interactive()


import java.util.Random;
public class MyMain {
  public static void main(String[] paramArrayOfString) {
    long x1 = (long)(Long.parseLong(paramArrayOfString[0])&((1L<<32)-1));
    long x2 = (long)(Long.parseLong(paramArrayOfString[1])&((1L<<32)-1));

    // = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
    //seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);

    for(int i= 0;i<(1<<16);i++){
        Random random = new Random(((x1<<16)+i)^0x5DEECE66DL);
        if(random.nextInt() == x2){
            System.out.println(random.nextInt());
        }
    }
  }
}

CopperStudy

里面包含6个challenge.

1. challenge1

[+]teamtoken:[++++++++++++++++]proof completed[++++++++++++++++]
[+]Generating challenge 1
[+]n=0x931a21e45b8c30eb30f1b9767c724f57dd770432df414a5969d770e5cf41d86aa8c198baba3709d602b6de17003406b3ba9190e99c4c9aaa470afe052fa2aec57a7c448bf1a887c5c4776a789b51bf4f76b334fc27a59469d6b4fb76af90ec2ec56a4c83f0cabfcb3669c2e24243c9dfe32cc817fd2196452df47e92eeb06eb5L
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x842683283571aeb5d8716f2a4667ff7e61fc63bb5a4cd89858c02881e0d536e344167e06e44ef5e276253563486c3b05971acfb96f8ed1a9e8c3143c026889ab11d5f72973bf6907f773ad0d570436cc64daf16e35ffff1fb48c66b36d9a8bfc568de1407b19f621ead2fa572fce24a921d742128a7b321f381e81bae0cb9f70L
[+]((m>>72)<<72)=0xb74706a05587a42246ed7ff2f03c4edf180f5248cfb7a8b86757ea456ba134c8a81f146b3172d1b59437efeb2e59b41e8dbb9cf2ac3254000000000000000000L

给定了明文的高位，低72位未知。思考了一会，发现不会，于是直接百度copper，发现了这个。上面给出了Coppersmith 算法的三种适用情况，并给出了相应的脚本。抄来改改就好了^_。

3 Challenge 2

[+]Generating challenge 2
[+]n=0xaf10597fa3ac1e95f9eeeb0747827fbfd6a6b74e9e7824e5e58c9423e4eea8f898ef5ad96900adc54721aa922af14987fbeecd1663e639f85d4e0fc2f5cc50fc1dfdf3e0b04d8395fdb8372447f0b398a7bff92cf7745c03a613e71a7017648db905ac867d69aab2c8c9ff0fc65c3313f4080cbb46d1a13a3b6c8e263915a413L
[+]e=65537
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x7be9e49497bebb936018a628148e89dc2f8cb919ac899b1ac3fa050ba7987e051e78adc51677d3ab3d2529d1f98be08459699ab381e6bd51c96cb6ae327112d0bfcdd68691f55a0b9e92516506939cbbd1612a4760d428df38dab6353b838f7bfdbfcfd3fad489258a8a289527c30a9a38bdbec751c3c3dacdb9f67a222fc8c0L
[+]((p>>128)<<128)=0xbb1c7149e21b37fb4480326fa4ce2f825ff449b22fbc55d5b9d51dea23d64d6c36d5e45a25d4a46f2559d26625dc6bd900000000000000000000000000000000L
[-]long_to_bytes(m).encode('hex')=

解法同上改一下脚本就好了。

3. Challenge 3

[++++++++++++++++]challenge 2 completed[++++++++++++++++]
[+]Generating challenge 3
[+]n=0x9dd9df9c335f720b2a01628f4433daeec452e55ed505ae66df8567c6ca66ea0796a242a7bcc41b973d0392ccd0a6e11c829890d3243cf86c90a03a5729240cb9eae191f5cff6294d83a04cee995a8d01f72e4d2166c60b7368b8061cf23e5b89d5057b7026ff7673c658f478cd0e3a6e0a21a97e21c9b2e5d8e94cbb50210d99L
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x169f8a6015b955747b211adb5e6a573eb03ea164170a35582dbc45d2a5d6ac4a01e0fae44b919d9afa419d73c1c02cb8e1095738b84236d53997862e0ac4dd108a47db0fb3515f3d8f29f620ec209bde20ebc93e64e9301751470f80212072e0981db41e0b307dbac81e3e126dd0e58cc96046b993cd2d48460731bb0a8c437cL
[+]d=invmod(e,(p-1)*(q-1))
[+]d&((1<<512)-1)=0x3a3d77ea2d0e834a43efa2accc7e463a7790f5f597abface5d56f3ed88aad629299a32ae6e21f0f9b43b7b402ba9d2e4d548f99298dce0ca92bcd26dd0d7c323L
[-]long_to_bytes(m).encode('hex')=

解法同上

4. challenge 4

[+]Generating challenge 4
[+]e=3
[+]m=random.getrandbits(512)
[+]n1=0x3cfc26953d034786a32dd22249d823ec272b8a46216efae5e57f9a8b8c7fed3b9b4a3c9361447159d714a614d7501e5b628a3da24b11a4ecd8c9c3f3cafb52674985752081ddff6eea6fc6c069d27b96ae039a53d05791c5207236890229abd337f2cad946ab550f8f4c414537fd3c0135f3b4f27e6919c15f2aa81a1ffe15afL
[+]c1=pow(m,e,n1)=0x374c6727e44c56e0de065f16bce1314b857792862f5d848a88d442605d7a54214806a0ad2c72090c39770e802aaa045deecaecc112c80a022ea3c4540823a175d11ba4fa347727931776854265c62228324ee77a8f19360f80f0a0152bfab2214474e3f744f8a0a577c26cdc2ab325326b40bc7d5d6fb9a005f9dce9418b6deaL
[+]n2=0x41e446d32fd2f4143558b8abf4f9cfd1feb827f49a3e61e115157ac948a183c196531acdd66d7749ede2f5913b01cdc49f98abb77a7bf6c9f1246ab1e74288d90885a0359cb244cc71f94b19fb552c2b6ace51ddf48893e3bae0561ae78cec67e71e7864da05fcfc13b8d3d741ef988043e944f8a53bb84def356170e2a9e5a3L
[+]c2=pow(m,e,n2)=0x2d9dbdaa0b89a0d12624a34146871f0378843199c516015e25770baefb00771713a705ff48eea7d9cad2a50c7b31d73612ac4c68ff29ba5a230546ff364fe6d2dc807b5eab1b3633baffe89c421bd683da0e4c828cd0709d08b2fb6941b94e3b73f87f1db368ef77d0597d1478192722b7ccfdab10dd4c9f6321676f5397e0ffL
[+]n3=0x1f7f8868ee329980957490a294da7507071ac5b90c029dddfef65a62a9c6010fa8cb735a00a7524e5633d3f807cc639d8956486bd29f46d16e731db107c8f1d58f995ec39c5582155ee06d4db32317fa1b3b9148052c18245c8b48f87844cb68d81f1f995044fa22eb18c197e437ba3badc12bc749572a49de66828e391b1dbL
[+]c3=pow(m,e,n3)=0x1e1e3ed0522464ccde39974aa9664f2fe9dad909ba4d42e9c2266dafccb5dc7e2074a9d4ac180653985e1b89def78d06143800d678365041abe2278dbcac81fce8f1122a117bd77b455ff7585a46d7e439265baa9c493d3f2fb2172a9bc07ba1483e1ed58a0eb5ea8efbd1d5f33cb62e01ab9ccecf7f2d396d4034b73cbf77cL

首先尝试发现 $n_1$ 、 $n_2$ 、 $n_3$ 没有公约数（如果有的话可以直接分解）。然后，利用中国剩余定理得到：
$m^e= n_2n_3c_1((n_2n_3)^{-1}mod n_1)+n_1n_3c_2((n_1n_3)^{-1}mod n_2)+n_2n_1c_1((n_2n_1)^{-1}mod n_3) mod n_1n_2n_3$
可以发现m是512位的，因此 $m^3$ 大概是1536位的，少于 $n_1n_2n_3$ 的3072位。因此，我们可以知道 $m^e= (n_2n_3c_1((n_2n_3)^{-1}mod n_1)+n_1n_3c_2((n_1n_3)^{-1}mod n_2)+n_2n_1c_1((n_2n_1)^{-1}mod n_3)） % n_1n_2n_3$
直接求立方根就可以得到m了。

5. chalenge 5

[++++++++++++++++]challenge 4 completed[++++++++++++++++]
[+]Generating challenge 5
[+]n=0x3298d508dc5255e5f53c2890326aceacf9439b9f2f06e2abf3e19ece5a503315852cbaf9ab9f730f9bde1082331f0697491dade2c57463d610b540697506ce3441ced4262ca150b1c28535f266e954967895f6d4b3fc86281cdfaa21fa8aa1b440de1bb0b0b4332969f24bff01d574f94235de3bc3da43401915adf253589b63L
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x1b124c087004fd532a26f2cb6cc5c9ee2176c2070d87c159bd0e74b8811ab3af84c96e05dd7bf6bb6b5a251c8558c357036aff678525c8734570e142e38e77419993892a29d9a9f54bd3d4c048895482466d749eb0cf5b12b427c1753f6ebe3eba2ad9dcdc87b7c2040bfab6a5c124eb21b821fa58e167d8cb57e9c551ab9dbfL
[+]x=pow(m+1,e,n)=0x2d6fcf825d2fcb98f37f951fc000520f4aab11222f92a1af01e0988943fdde016664b706f4197bd085e79f57daedbecf4ee59cc9f010998c22f1c2df6223df57e86b9efd8bcca779f16e6da8a54778459b4d956a255d8ecc3d3a9e9a72a7c70cb2bec8bbaa2bb5c2f2d3f95769cee6fdd7fd04bbd6d84070e50739b5b059c6e6L
[-]long_to_bytes(m).encode('hex')=

题目中给出了m和m+1加密后的结果。即我们知道：
$m^3\equiv c_1\ mod\ n \\ (m+1)^3 \equiv c_2\ mod\ n$
二者相减得到：
$3m^2+3m+1 \equiv c_2-c_1\ mod\ n$
两边减1并乘以3模n的逆得到：
$m^2+m \equiv (c_2-c_1-1)*(3^{-1}\ mod\ n) mod\ n$
我们知道m是512位的，由此可以推出 $m^2+m$ 不超过1024位。进而可以得到：
$m^2+m = k*n+(c_2-c_1-1)*(3^{-1}\ mod\ n) %n$
k = 0或1（不确定自己分析的对不对，所以写代码的时候把k的范围稍微扩大了一点点）
然后，对每一个k值，尝试求解上面的方程就可以得到结果了。因为 $m^2+m$ 在 $(0,+\infty)$ 单调递增，因此求解方法用二分法即可。

6. challenge 6

[++++++++++++++++]challenge 5 completed[++++++++++++++++]
[+]Generating challenge 6
[+]n=0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27L
[+]d=random.getrandbits(1024*0.270)
[+]e=invmod(d,phin)
[+]hex(e)=0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bbL
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866cL

注意到题目中提示 $p$ 的位数为0.27*1024，相当于 $p<n^{0.27}$ 。不知道怎么办，后来在mhx的提示下发现Boneh and Durfee attack在 $p<n^{0.292}$ 时分解n。然后又是直接抄个脚本过来分解掉了。
代码如下（不包含Sage脚本，因为上面提供的连接中都有）：

from Crypto.Util import  number
from pwn import *
import hashlib
import libnum
from aux import *
import tqdm
import gmpy2

conn = remote('119.3.245.36', 12345)


x0 = 3031202121516888756254+0xb74706a05587a42246ed7ff2f03c4edf180f5248cfb7a8b86757ea456ba134c8a81f146b3172d1b59437efeb2e59b41e8dbb9cf2ac3254000000000000000000

p = 157455850951539875413707605384569848509+0xbb1c7149e21b37fb4480326fa4ce2f825ff449b22fbc55d5b9d51dea23d64d6c36d5e45a25d4a46f2559d26625dc6bd900000000000000000000000000000000L
n = 0xaf10597fa3ac1e95f9eeeb0747827fbfd6a6b74e9e7824e5e58c9423e4eea8f898ef5ad96900adc54721aa922af14987fbeecd1663e639f85d4e0fc2f5cc50fc1dfdf3e0b04d8395fdb8372447f0b398a7bff92cf7745c03a613e71a7017648db905ac867d69aab2c8c9ff0fc65c3313f4080cbb46d1a13a3b6c8e263915a413
q = n/p
c = 0x7be9e49497bebb936018a628148e89dc2f8cb919ac899b1ac3fa050ba7987e051e78adc51677d3ab3d2529d1f98be08459699ab381e6bd51c96cb6ae327112d0bfcdd68691f55a0b9e92516506939cbbd1612a4760d428df38dab6353b838f7bfdbfcfd3fad489258a8a289527c30a9a38bdbec751c3c3dacdb9f67a222fc8c0
x1 = pow(c,gmpy2.invert(65537,(p-1)*(q-1)),n)

d = 73897859833360735083833018291216138538391694441421128347796113898176347610218862647497820864455327205623491646417194479391497879610944659647766341364110862866967065387388720221408859326315301232384151863747183910278699184043306720913086501616478917318589938736632770485961912898351468620093203923268728767267
c = 0x169f8a6015b955747b211adb5e6a573eb03ea164170a35582dbc45d2a5d6ac4a01e0fae44b919d9afa419d73c1c02cb8e1095738b84236d53997862e0ac4dd108a47db0fb3515f3d8f29f620ec209bde20ebc93e64e9301751470f80212072e0981db41e0b307dbac81e3e126dd0e58cc96046b993cd2d48460731bb0a8c437c
n = 0x9dd9df9c335f720b2a01628f4433daeec452e55ed505ae66df8567c6ca66ea0796a242a7bcc41b973d0392ccd0a6e11c829890d3243cf86c90a03a5729240cb9eae191f5cff6294d83a04cee995a8d01f72e4d2166c60b7368b8061cf23e5b89d5057b7026ff7673c658f478cd0e3a6e0a21a97e21c9b2e5d8e94cbb50210d99L
x2 = pow(c,d,n)

n1 = 0x3cfc26953d034786a32dd22249d823ec272b8a46216efae5e57f9a8b8c7fed3b9b4a3c9361447159d714a614d7501e5b628a3da24b11a4ecd8c9c3f3cafb52674985752081ddff6eea6fc6c069d27b96ae039a53d05791c5207236890229abd337f2cad946ab550f8f4c414537fd3c0135f3b4f27e6919c15f2aa81a1ffe15af
n2 = 0x41e446d32fd2f4143558b8abf4f9cfd1feb827f49a3e61e115157ac948a183c196531acdd66d7749ede2f5913b01cdc49f98abb77a7bf6c9f1246ab1e74288d90885a0359cb244cc71f94b19fb552c2b6ace51ddf48893e3bae0561ae78cec67e71e7864da05fcfc13b8d3d741ef988043e944f8a53bb84def356170e2a9e5a3
n3 = 0x1f7f8868ee329980957490a294da7507071ac5b90c029dddfef65a62a9c6010fa8cb735a00a7524e5633d3f807cc639d8956486bd29f46d16e731db107c8f1d58f995ec39c5582155ee06d4db32317fa1b3b9148052c18245c8b48f87844cb68d81f1f995044fa22eb18c197e437ba3badc12bc749572a49de66828e391b1db
c1 = 0x374c6727e44c56e0de065f16bce1314b857792862f5d848a88d442605d7a54214806a0ad2c72090c39770e802aaa045deecaecc112c80a022ea3c4540823a175d11ba4fa347727931776854265c62228324ee77a8f19360f80f0a0152bfab2214474e3f744f8a0a577c26cdc2ab325326b40bc7d5d6fb9a005f9dce9418b6dea
c2 = 0x2d9dbdaa0b89a0d12624a34146871f0378843199c516015e25770baefb00771713a705ff48eea7d9cad2a50c7b31d73612ac4c68ff29ba5a230546ff364fe6d2dc807b5eab1b3633baffe89c421bd683da0e4c828cd0709d08b2fb6941b94e3b73f87f1db368ef77d0597d1478192722b7ccfdab10dd4c9f6321676f5397e0ff
c3 = 0x1e1e3ed0522464ccde39974aa9664f2fe9dad909ba4d42e9c2266dafccb5dc7e2074a9d4ac180653985e1b89def78d06143800d678365041abe2278dbcac81fce8f1122a117bd77b455ff7585a46d7e439265baa9c493d3f2fb2172a9bc07ba1483e1ed58a0eb5ea8efbd1d5f33cb62e01ab9ccecf7f2d396d4034b73cbf77c

x = c1*gmpy2.invert(n2*n3,n1)*n3*n2 + c2*gmpy2.invert(n1*n3,n2)*n1*n3 + c3 * gmpy2.invert(n1*n2,n3)*n1*n2
x = int(x%(n1*n2*n3))
def cubeRoot(x):
    l,r = 0,x
    while l<r:
        mid = (l+r)//2
        if mid**3 == x:
            return mid
        elif mid**3 < x:
            l = mid+1
        else:
            r = mid-1
    return l
x3 = cubeRoot(x)
assert x3**3 %n1 == c1 and x3**3%n2 == c2 and x3**3%n3 == c3

n = 0x3298d508dc5255e5f53c2890326aceacf9439b9f2f06e2abf3e19ece5a503315852cbaf9ab9f730f9bde1082331f0697491dade2c57463d610b540697506ce3441ced4262ca150b1c28535f266e954967895f6d4b3fc86281cdfaa21fa8aa1b440de1bb0b0b4332969f24bff01d574f94235de3bc3da43401915adf253589b63
e = 3
c = 0x1b124c087004fd532a26f2cb6cc5c9ee2176c2070d87c159bd0e74b8811ab3af84c96e05dd7bf6bb6b5a251c8558c357036aff678525c8734570e142e38e77419993892a29d9a9f54bd3d4c048895482466d749eb0cf5b12b427c1753f6ebe3eba2ad9dcdc87b7c2040bfab6a5c124eb21b821fa58e167d8cb57e9c551ab9dbf
x = 0x2d6fcf825d2fcb98f37f951fc000520f4aab11222f92a1af01e0988943fdde016664b706f4197bd085e79f57daedbecf4ee59cc9f010998c22f1c2df6223df57e86b9efd8bcca779f16e6da8a54778459b4d956a255d8ecc3d3a9e9a72a7c70cb2bec8bbaa2bb5c2f2d3f95769cee6fdd7fd04bbd6d84070e50739b5b059c6e6
tmp = (x-c-1)*gmpy2.invert(3,n)%n

def findm(x,n):
    l,r = 0,n
    while l<r:
        mid = (l+r)//2
        t = mid**2+mid
        if t==x:
            return mid
        elif t<x:
            l = mid +1
        else:
            r = mid -1
    return l

for i in range(5):
    m = findm(tmp+i*n,n)
    if (m**2+m) == tmp:
        break
assert (m**3)%n == c
x4 = m

n = 0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27
e = 0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bb
c = 0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866c
d = 776765455081795377117377680209510234887230129318575063382634593357724998207571

assert c == pow(c,e*d,n)
x5 = pow(c,d,n)

solveSHA(conn)
conn.recvuntil('long_to_bytes(m).encode(\'hex\')=')
conn.sendline(number.long_to_bytes(x0).encode('hex'))
conn.recvuntil("long_to_bytes(m).encode('hex')=")
conn.sendline(number.long_to_bytes(x1).encode('hex'))
conn.recvuntil("long_to_bytes(m).encode('hex')=")
conn.sendline(number.long_to_bytes(x2).encode('hex'))
conn.recvuntil("long_to_bytes(m).encode('hex')=")
conn.sendline(number.long_to_bytes(x3).encode('hex'))
conn.recvuntil("long_to_bytes(m).encode('hex')=")
conn.sendline(number.long_to_bytes(x4).encode('hex'))
conn.recvuntil("long_to_bytes(m).encode('hex')=")
conn.sendline(number.long_to_bytes(x5).encode('hex'))
conn.interactive()

强网先锋-辅助

题目中给出了 $n_1=p_1*q$ , $n_2=p_2*q$ 的值，并用 $n$ 和 $e$ 加密了明文。因此，先对 $n_1$ 和 $n_2$ 求最大公约数可以得到 $q$ ，进而分解 $n_1$ ，最后得到 $d$ 解密密文。

c1 = 2482083893746618248544426737023750400124543452082436334398504986023501710639402060949106693279462896968839029712099336235976221571564642900240827774719199533124053953157919850838214021934907480633441577316263853011232518392904983028052155862154264401108124968404098823946691811798952747194237290581323868666637357604693015079007555594974245559555518819140844020498487432684946922741232053249894575417796067090655122702306134848220257943297645461477488086804856018323986796999103385565540496534422406390355987976815450744535949785073009043007159496929187184338592859040917546122343981520508220332785862546608841127597
e = 65537
n1 = 14967030059975114950295399874185047053736587880127990542035765201425779342430662517765063258784685868107066789475747180244711352646469776732938544641583842313791872986357504462184924075227433498631423289187988351475666785190854210389587594975456064984611990461126684301086241532915267311675164190213474245311019623654865937851653532870965423474555348239858021551589650169602439423841160698793338115204238140085738680883313433574060243600028500600824624358473403059597593891412179399165813622512901263380299561019624741488779367019389775786547292065352885007224239581776975892385364446446185642939137287519945974807727
c2 = 3829060039572042737496679186881067950328956133163629908872348108160129550437697677150599483923925798224328175594483217938833520220087230303470138525970468915511111320396185482564783975435346354440035776909781158407636044986403819840648379609630039348895415045723208843631191252142600667607807479954194447237061080618370787672720344741413537975922184859333432197766580150534457001196765621678659952108010596273244230812327182786329760844037149719587269632133595149294067490955644893402708720284179715002149224068928828656515326446881791228638008572889331511945042911372915003805505412099102954073299010951896955362470
n2 = 14624662628725820618622370803948630854094687814338334827462870357582795291844925274690253604919535785934208081825425541536057550227048399837243392490762167733083030368221240764693694321150104306044125934201699430146970466657410999261630825931178731857267599750324918610790098952520113593130245010530961350592735239454337631927669542026935873535964487595433984902529960726655481696404006628917922241666148082741874033756970724357470539589848548704573091633917869387239324447730587545472564561496724882799495186768858324490838169123077051890332313671220385830444331578674338014080959653201802476516237464651809255679979
import gmpy2
from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes

p = gmpy2.gcd(n1,n2)

assert n1%p ==0 and n2%p == 0
q = n1//p

print "flag=%s"%(long_to_bytes(pow(c1,gmpy2.invert(e,(p-1)*(q-1)),n1),))

2019年强网杯crypto部分题解

一、random study

1. challenge 1

2.challenge 2

3. challenge3

CopperStudy

1. challenge1

3 Challenge 2

3. Challenge 3

4. challenge 4

5. chalenge 5

6. challenge 6

强网先锋-辅助

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

2019年强网杯crypto部分题解

一 、random study

1. challenge 1

2.challenge 2

3. challenge3

CopperStudy

1. challenge1

3 Challenge 2

3. Challenge 3

4. challenge 4

5. chalenge 5

6. challenge 6

强网先锋-辅助

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

一、random study