crypto
1 Lost_Modulus_Again
1.1 题目
from Crypto.Util.number import *
class Key:
def __init__(self, bits):
assert bits >= 512
self.p = getPrime(bits)
self.q = getPrime(bits)
self.n = self.p * self.q
self.e = 0x100007
self.d = inverse(self.e, (self.p-1)*(self.q-1))
self.dmp1 = self.d%(self.p-1)
self.dmq1 = self.d%(self.q-1)
self.iqmp = inverse(self.q, self.p)
self.ipmq = inverse(self.p, self.q)
def encrypt(self, data):
num = bytes_to_long(data)
result = pow(num, self.e, self.n)
return long_to_bytes(result)
def decrypt(self, data):
num = bytes_to_long(data)
v1 = pow(num, self.dmp1, self.p)
v2 = pow(num, self.dmq1, self.q)
result = (v2*self.p*self.ipmq+v1*self.q*self.iqmp) % self.n
return long_to_bytes(result)
def __str__(self):
return "Key([e = {0}, n = {1}, x = {2}, y = {3}])".format(self.e, self.d, self.iqmp, self.ipmq)
def main():
key = Key(1024)
flag = open('flag').read()
encrypt_flag = key.encrypt(flag)
assert key.decrypt(encrypt_flag) == flag
print key
print encrypt_flag.encode('hex')
if __name__ == '__main__':
main()
output文件内容
Key([e = 1048583,
n=20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927,
x=22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743,
y=138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331])
32074de818f2feeb788e36d7d3ee09f0000381584a72b2fba0dcc9a2ebe5fd79cf2d6fd40c4dbfea27d3489704f2c1a30b17a783baa67229d02043c5bc9bdb995ae984d80a96bd79370ea2c356f39f85a12d16983598c1fb772f9183441fea5dfeb5b26455df75de18ce70a6a9e9dbc0a4ca434ba94cf4d1e5347395cf7aafa756c8a5bd6fd166bc30245a4bded28f5baac38d024042a166369f7515e8b0c479a1965b5988b350064648738f6585c0a0d1463bd536d11a105bb926b44236593b5c6c71ef5b132cd9c211e8ad9131aa53ffde88f5b0df18e7c45bcdb6244edcaa8d386196d25297c259fca3be37f0f2015f40cb5423a918c51383390dfd5a8703
1.2 分析
根据rsa加密体制，可以根据程序得出下面的式子。
phi(n)=(p-1)(q-1)
e * d == 1 (mod phi(n))
==》e * d == k * phi(n) + 1
其中k是一个不确定的值，但是范围很小,为[2,e]
q * x == 1 + k1 * p
p * y == 1 + k2 * q
==》q * (x + k2) == p * (y + k1)
因为（p,q）=1, 并且 q|(y + k1)，p|(x + k2)，0 < x + k2 < 2 * p ，0 < y + k1 < 2 * q，所以可以得到
p = x + k
q = y + k1
==》phi(n) = (p - 1) * (q - 1)
= (x + k2 - 1) * (y + k1 - 1)
= (x - 1) * (y - 1) + (x - 1) * k1 + (y - 1) * k2 + k1 * k2
目前求phin的问题，变成了求解k1,k2的问题
q = y + k1
q * x == 1 + k1 * p
==》q * x = 1 + (q - y) * p
==》x * y = 1 + k1 * k2
这样就得到了k1,k2的一个关系
x * y = 1 + k1 * k2
phi(n)= (x - 1) * (y - 1) + (x - 1) * k1 + (y - 1) * k2 + k1 * k2
==》phi(n) = x * y - 1 + (y - 1) * (x * y - 1) / k1 + k1 * (x - 1) + (x - 1) * (y - 1)
==》(x - 1) * k1 ** 2 + (x * y - 1 - phi(n) + (x - 1) * (y - 1)) * k1 + (y - 1) * (x * y - 1) = 0
得到一个二次方程，k1,k2肯定是个整数，这样就可以穷举了。直接恢复出k1，k2，p，q
1.3 求解
#!/usr/bin/env python
#!/usr/bin/env python
from Crypto.Util.number import long_to_bytes
import gmpy2
import string
e = 1048583
d = 20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927
x = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743
y = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331
c = 0x32074de818f2feeb788e36d7d3ee09f0000381584a72b2fba0dcc9a2ebe5fd79cf2d6fd40c4dbfea27d3489704f2c1a30b17a783baa67229d02043c5bc9bdb995ae984d80a96bd79370ea2c356f39f85a12d16983598c1fb772f9183441fea5dfeb5b26455df75de18ce70a6a9e9dbc0a4ca434ba94cf4d1e5347395cf7aafa756c8a5bd6fd166bc30245a4bded28f5baac38d024042a166369f7515e8b0c479a1965b5988b350064648738f6585c0a0d1463bd536d11a105bb926b44236593b5c6c71ef5b132cd9c211e8ad9131aa53ffde88f5b0df18e7c45bcdb6244edcaa8d386196d25297c259fca3be37f0f2015f40cb5423a918c51383390dfd5a8703
#(x - 1) * k1 ** 2 + (x * y - 1 - phi_n + (x - 1) * (y - 1)) * k1 + (y - 1) * (x * y - 1) = 0
for k in range(2,e):
if((e*d -1)%k==0):
phi_n=(e*d -1)//k
f_a=x - 1
f_b=x * y - 1 - phi_n + (x - 1) * (y - 1)
f_c=(y - 1) * (x * y - 1)
derta = f_b ** 2 - 4 * f_a * f_c
x1 = (-f_b + gmpy2.isqrt(derta)) // (2 * f_a)
x2 = (-f_b - gmpy2.isqrt(derta)) // (2 * f_a)
if (x * y - 1) % x1 == 0:
x2 = (x * y - 1) // x1
elif (x * y - 1) % x2 == 0:
x1, x2 = x2, (x * y - 1) // x2
else:
assert True
p, q = x + x2, y + x1
N = p * q
flag = long_to_bytes(pow(c, d, N)).strip()
print flag+"\n"
在穷举结果中查看。可以看到flag。
2 Very_Simple_Haskell
2.1 题目
import Data.Char
import System.IO
n :: Integer
n = 134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667
k :: Int
k = 131
primes :: [Integer]
primes = take k $ sieve (2 : [3, 5..])
where
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
stringToInteger :: String -> Integer
stringToInteger str = foldl (\x y -> (toInteger $ ord y) + x*256) 0 str
integerToString :: Integer -> String
integerToString num = f num ""
where
f 0 str = str
f num str = f (div num 256) $ (:) (chr $ fromIntegral $ num `mod` 256) str
numToBits :: Integer -> [Int]
numToBits num = f num []
where
f 0 arr = arr
f x arr = f (div x 2) ((fromInteger $ x `mod` 2) : arr)
extendBits :: Int -> [Int] -> [Int]
extendBits blockLen arr
| len == 0 = arr
| len > 0 = (replicate (blockLen-len) 0) ++ arr
where len = (length arr) `mod` blockLen
calc :: Integer -> [Int] -> Integer
calc num [] = num
calc num arr = calc result restArr
where
num2 = num*num `mod` n
(block, restArr) = splitAt k arr
zipped = zipWith (\x y -> ((fromIntegral x)*y) `mod` n) block primes
mul = product $ filter (/=0) zipped
result = num2*mul `mod` n
magic :: String -> String
magic input = result
where
num = stringToInteger input
bits = numToBits num
extended = reverse $ extendBits 8 bits
oriLen = length extended
extendedBits = extendBits k extended
oriLenBits = numToBits $ fromIntegral oriLen
extendedOriLenBits = extendBits k oriLenBits
finalBits = extendedOriLenBits ++ extendedBits
result = show $ calc 1 (reverse finalBits)
main = do
flag <- readFile "flag"
putStrLn.show $ length flag
putStrLn $ magic ("the flag is hitcon{" ++ flag ++ "}")
haskell语言写的，可以看出大致的逻辑
output文件如下
6
84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096
2.2 分析
这是一个基于背包问题的公钥密码算法
具体可见 Naccache-Stern Knapsack Cryptosystem.
关于细节的实现，链接如下 here. 题目暗示私钥s = 1。
已经知道了flag的长度，明文被分为了三个部分，第一部分（ "the flag is hitcon{"）和最后部分（"}"）已知。将最后一个块解密，第一个块加密，可以解密第二个块。
2.3 求解
#!/usr/bin/env python
from Crypto.Util.number import long_to_bytes as l2b
from Crypto.Util.number import bytes_to_long as b2l
from Crypto.Util.number import inverse
from gmpy2 import gcd
from string import printable
#from config import c, n, primes, k
n = 134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667
primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739]
k = 131
c=84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096
def encode(m):
m = list("{:b}".format(b2l(m)))
m = list(map(int, m))
m = m[::-1]
m += (8 - len(m) % 8) * [0]
extended = m
oriLen = len(m)
extended = (k - len(extended) % k) * [0] + extended
extendedBits = extended
oriLenBits = list("{:b}".format(oriLen))
oriLenBits = list(map(int, oriLenBits))
oriLenBits = (k - len(oriLenBits) % k) * [0] + oriLenBits
extendedOriLenBits = oriLenBits
finalBits = extendedOriLenBits + extendedBits
finalBits = finalBits[::-1]
return finalBits
def form(flag):
return "the flag is hitcon{" + flag + "}"
def calc(num, arr):
num2 = num ** 2 % n
block, restArr = arr[:k], arr[k:]
mul = 1
for (i, j) in zip(block, primes):
if i * j != 0:
mul *= i * j
result = num2 * mul % n
if len(restArr) == 0:
return result
else:
return calc(result, restArr)
def calc2(num, arr):
num2 = num ** 2 % n
block, restArr = arr[:k], arr[k:]
mul = 1
for (i, j) in zip(block, primes):
if i * j != 0:
mul *= i * j
result = num2 * mul % n
return result
def encrypt(finalBits):
res = calc(1, finalBits)
return res
def decrypt(cipher):
msg = []
for (i, prime) in enumerate(primes):
data = (gcd(prime, cipher ** s) - 1) // (prime - 1)
msg.append(int(data))
return msg
flag = "SAMPLE"
finalBits = encode(form(flag))
res = encrypt(finalBits)
# We know first k = 131 bits of plaintext
result_ = calc2(1, finalBits[:k])
# private key s
s = 1
# We also know final k = 131 bits of plaintext, since knowing len
mul = 1
for (i, j) in zip(finalBits[2 * k: 3 * k], primes):
if i * j != 0:
mul *= i * j
num2_ = c * inverse(mul, n) % n
print len(decrypt(result_))
print len(finalBits[:k])
assert decrypt(result_) == finalBits[:k]
# simply meet in the middle and get ciphertext
test = num2_ * inverse(result_ ** 4, n) % n
# decrypt to get intermediate k = 131 bits
m = decrypt(test)
# "o"'s 5 bits + "n{"
m = m[5 + 8 * 2:]
flag = ""
# len(flag) == 6
for i in range(6):
flag += chr(int("".join(list(map(str, m[8 * i:8 * (i + 1)]))), 2))
flag = "hitcon{" + flag + "}"
print(flag)
balsn战队脚本如下
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import libnum
primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
n = 134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667
enc=84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096
bit2int = lambda x: int(''.join(map(str, x)), 2)
m = 129105988525739869308153101831605950072860268575706582195774923614094296354415364173823406181109200888049609207238266506466864447780824680862439187440797565555486108716502098901182492654356397840996322893263870349262138909453630565384869193972124927953237311411285678188486737576555535085444384901167109670365
z = enc * libnum.invmod(m, n) % n
bits = [(z % p == 0) * 1 for p in primes]
for i in range(0, 8*20, 8):
print(chr(bit2int(bits[5:][i:i+8])))
