RSA系列之进阶实战
RSA系列之进阶实战
导入
基础题与其解析别的网址都很多，笔者仅挑了不常见的例子和典型的例子，多的也不再赘述。请初入门的师傅想巩固基础自行别处搜索刷题。从进阶篇开始将直接上近几年题目，同样不会选择常见的比赛题目，会挑选小比赛或者小练习，甚至笔者出的题。但都是我所认为有一定参考意义并且给下一届密码手试手过。笔者将尽力整理成册，并辅以自己的理解和总结。希望能帮助到各位读者，若有笔误甚至错误，敬请谅解并联系我更改，共勉。
基础知识不回顾
到这想必也有一定基础了，此篇过后不再对rsa基础知识作赘述
二项式+二次剩余=？
题目
from Crypto.Util.number import *
from secret import flag
p = getPrime(512)
q = getPrime(512)
n = p * (q**2)
s = 65537
hint1 = pow((p+q), s, n)
hint2 = pow((p-q), s, n)
while True:
z = getRandomRange(1, n - 1)
if pow(z, (p-1)//2, p) == p-1 and pow(z, (q-1)//2, q) == q-1:
break
def secert_0_1_encrypt(m, n, z):
secret = getRandomRange(1, n - 1)
c = pow(secret, 2, n) * pow(z, m, n) % n
return c
m = bytes_to_long(flag)
plaintext = int(bin(int(m))[2:])
ciphertext = [0] * len(str(plaintext))
for i in range(len(str(plaintext))):
ciphertext[i] = secert_0_1_encrypt(plaintext % 10, n, z)
plaintext = plaintext // 10
print("n=", n)
print("hint1", hint1)
print("hint2", hint2)
print("z=", z)
print("ciphertext", ciphertext)
分析
首先给了两个hint：
- hint1 = ( p + q ) ^ e ( mod n )
- hint2 = ( p - q ) ^ e ( mod n )
那么二项式展开就有：
- hint1 = p^e + q^e ( mod n )
- hint2 = p^e - q^e ( mod n )
相加后与n求gcd即可得到n的分解。
然后进入下一部分，首先他按如下方式生成了z：
while True:
z = getRandomRange(1, n - 1)
if pow(z, (p-1)//2, p) == p-1 and pow(z, (q-1)//2, q) == q-1:
break这里其实就是用欧拉判别式保证：
- z^( p-1 / 2 ) = -1 mod p
- z^( p-1 / 2 ) = -1 mod q
也就是说，z既不是模p下的二次剩余，也不是模q下的二次剩余。
然后，他将flag转换成二进制串，并把这个二进制串视为一个十进制数，然后对每一位逐位加密。也就是说这个十进制串的每一位都是0或1，逐位加密的方式如下，每一十进制位记作mi：
$$
cipger i = secreti^2z^mi(modn)
$$
然后由于我们有了n的分解，我们将这个式子转化到模p下(模q下也一样)：
$$
cipger i = secreti^2z^mi(modp)
$$
那么，当mi等于0和等于1时，cipheri分别是：
- cipger i = secreti^2(modp)
- cipger i = secreti^2 * z (modp)
而由于z不是模p下的二次剩余，所以当mi分别为0和1时，cipheri分别是\不是二次剩余。因此我们可以用欧拉判别式来判断cipheri是不是二次剩余，以此来还原每一位mi：
cipgeri ^( p-1 / 2)= 1 ( modp )
或：
cipgeri ^( p-1 / 2)= -1 ( modp )
exp：
from Crypto.Util.number import *
from cipher import *
from gmpy2 import *
p = GCD(hint1 + hint2,n)
q = iroot(n // p , 2)[0]
flag = ""
for i in ciphertext:
if(pow(i,(p-1)//2,p) == 1):
flag += "0"
else:
flag += "1"
print(long_to_bytes(int(flag[::-1],2)))
广度
由小窥大，中等常规赛题的出题思路就是套娃，或者用几种加密方式去加密分段flag和数据。很明显，需要我们更多的基础知识作为打底，这道是较为典型的题目，用了二项式和二次剩余判断。当然，比赛的时候也不要太呆，如果允许的话，我们可以看到z^( p-1 / 2 ) = -1 mod p，一搜便是二次剩余。
双首尾剪枝的双解
题目
from sympy import *
from Crypto.Util.number import *
from secret import flag
def gen():
p = getPrime(512)
q = nextprime(int(str(p)[::-1]))
a = p&(10**6)
b = q%(10**6)
return p, q, a, b
p, q, a, b = gen()
n = p * q
e = 65537
c = pow(flag, e, n)
print('a =', a)
print('b =', b)
print('n =', n)
print('c =', c)
'''
a = 393792
b = 657587
n = 369861662178631957928245949770898273807810914183024109983427665445735262653137205864716795669578458854257293391751966280054435051199001813062804877555180285022533020724584142987601931508644551710279816508694942797383860411279321090090880184911983657558416043011288974643282183209071299542379616927857228873411
c = 71672159337725868237152385281240906653912972455699529924728534161923598107229667985188160316648005550663968313537597184857765083556920840254397949219027087098695062021613177519248117588571374167137534818793726427056016629301262986053118989821488864074425276527050110912787300008659230186841168308795745942580
'''
解析
本题重点在于由gen函数获得n的分解：
def gen():
p = getPrime(512)
q = nextprime(int(str(p)[::-1]))
a = p&(10**6)
b = q%(10**6)
return p, q, a, b
注意到p和q具有如下关系：
- q是p的十进制逆序的nextprime
- 我们知道，nextprime一般最多也就产生不超过两千的偏移，这里就要敏感地想到高低位、4位等关键词
同时，题目还给了两个额外信息a、b，分别是：
a = p&(10**6)
b = q%(10**6)
这里我简单写一段常规的首尾剪枝便于大家理解其与常规首尾剪枝的异同。
m = bytes_to_long(flag)
p = getPrime(256)
q = getPrime(256)
n = p * q
e = 65537
_q = int(bin(q)[2:][::-1] , 2)
c = pow(m,e,n)
print(p ^ _q)
print(n)
print(c)
区别在于两点：一是由二进制逆序换成十进制逆序；二是q在取逆序后还作了一次nextprime操作。
因此当我们爆破出p的低六位，相应的，我们也就有了q的高六位。而由于给出的额外信息b暴露了q的低六位（自行计算位数），因此我们可以对偏移量进行爆破，从而得到正确的p的高六位的逆序。爆破的依据为：
- 对可能的p高六位后面填充全0，与q高六位后面填充全0，乘积应小于n
- 对可能的p高六位后面填充全9，与q高六位后面填充全9，乘积应大于n
这一步解决后，问题就变成了：已知p、q的高六位和低六位以及p、q的乘积n，要求还原p、q，并且他们之间存在逆序关系。
搜索方式：
- 从两端向中间搜索
- 每一次搜索10x10种可能，分别对应高位部分的一个十进制位和低位部分的一个十进制位
剪枝条件：
- 将p、q未搜索到的位全填0，乘积应小于n
- 将p、q未搜索到的位全填9，乘积应大于n
- p、q 低 k 位乘积再取低 k 位，应与 n 的低 k 位相同
exp：
from Crypto.Util.number import *
import sys
sys.setrecursionlimit(100000)
def dec(p,q,c,n):
phi = (p-1)*(q-1)
d = inverse(65537,phi)
print(long_to_bytes(pow(c,d,n)))
def find(ph,qh,pl,ql):
#check1
padding0 = (dec_len-len(ph)-len(pl))*"0"
padding9 = (dec_len-len(ph)-len(pl))*"9"
if(int(qh+padding0+ql)*int(ph+padding0+pl) > n or int(qh+padding9+ql)*int(ph+padding9+pl) < n):
return
#check2
mask = 10**len(pl)
if(int(ql)*int(pl) % mask != n % mask):
return
#return(因为p、q长度为奇数，才这样，否则可以直接判断)
if(len(ph+pl) == dec_len-1):
for i in range(10):
if(n % int(ph+str(i)+pl) == 0):
p = int(ph+str(i)+pl)
q = n // p
dec(p,q,c,n)
exit()
#search
for i in range(10):
for j in range(10):
find(ph + str(i), qh + str(j), str(j) + pl, str(i) + ql)
a = 393792
b = 657587
n = 369861662178631957928245949770898273807810914183024109983427665445735262653137205864716795669578458854257293391751966280054435051199001813062804877555180285022533020724584142987601931508644551710279816508694942797383860411279321090090880184911983657558416043011288974643282183209071299542379616927857228873411
c = 71672159337725868237152385281240906653912972455699529924728534161923598107229667985188160316648005550663968313537597184857765083556920840254397949219027087098695062021613177519248117588571374167137534818793726427056016629301262986053118989821488864074425276527050110912787300008659230186841168308795745942580
dec_len = 155
#find plow
qlow = str(b)
for i in range(1000000):
if(i*b % (10**6) == n % (10**6)):
plow = str(i)
qhigh = plow[::-1]
#find phigh
for i in range(2000):
phigh = str(b-i)[::-1]
if(int(phigh + "0" * (dec_len-6)) * int(qhigh + "0" * (dec_len-6)) < n and int(phigh + "9" * (dec_len-6)) * int(qhigh + "9" * (dec_len-6)) > n):
break
find(phigh,qhigh,plow,qlow)
#flag{7495268d-9987-497e-be6d-2abd1ad91496}
深度
这是一道改编题，出题人将常见的二进制剪枝变为十进制（在当时那个时间段），相比于对知识的积累，这类题型更考验对每一个知识点的理解深度，不是走马观花地看题和记住脚本，更需要一种热爱。并且对于新颖题型始终报以激情和挑战的决心。就像做完了其实还可以思考一个问题，我们真的需要q的低六位这个信息吗？其实并不用，因为可以发现深搜速度很快，那么我们不用q的低六位这个信息，而直接爆破q的低四位，做法也是一样的(之所以爆破低四位是因为偏移量最多也就几千，低四位完全足够)，那么上文所提到的nextprime函数就可以用到了。就有了这道题的第二个解法：
然后脚本需要注意两个细节问题：
- 要填充至4个字符
- b-i可能会小于0，这种情况需要对应加上10000变成四位正数
不用信息b的exp如下：
from Crypto.Util.number import *
import sys
from tqdm import *
sys.setrecursionlimit(100000)
def dec(p,q,c,n):
phi = (p-1)*(q-1)
d = inverse(65537,phi)
print(long_to_bytes(pow(c,d,n)))
def find(ph,qh,pl,ql):
#check1
padding0 = (dec_len-len(ph)-len(pl))*"0"
padding9 = (dec_len-len(ph)-len(pl))*"9"
if(int(qh+padding0+ql)*int(ph+padding0+pl) > n or int(qh+padding9+ql)*int(ph+padding9+pl) < n):
return
#check2
mask = 10**len(pl)
if(int(ql)*int(pl) % mask != n % mask):
return
#return(因为p、q长度为奇数，才这样，否则可以直接判断)
if(len(ph+pl) == dec_len-1):
for i in range(10):
if(n % int(ph+str(i)+pl) == 0):
p = int(ph+str(i)+pl)
q = n // p
dec(p,q,c,n)
exit()
#search
for i in range(10):
for j in range(10):
find(ph + str(i), qh + str(j), str(j) + pl, str(i) + ql)
n = 369861662178631957928245949770898273807810914183024109983427665445735262653137205864716795669578458854257293391751966280054435051199001813062804877555180285022533020724584142987601931508644551710279816508694942797383860411279321090090880184911983657558416043011288974643282183209071299542379616927857228873411
c = 71672159337725868237152385281240906653912972455699529924728534161923598107229667985188160316648005550663968313537597184857765083556920840254397949219027087098695062021613177519248117588571374167137534818793726427056016629301262986053118989821488864074425276527050110912787300008659230186841168308795745942580
dec_len = 155
#find plow
for b in trange(10000):
try:
qlow = str(b).zfill(4)
for i in range(10000):
if(i*b % (10**4) == n % (10**4)):
plow = str(i).zfill(4)
qhigh = plow[::-1]
#find phigh
for i in range(2000):
if(b-i>=0):
phigh = str(b-i)[::-1].zfill(4)
else:
phigh = str(b-i+10000)[::-1].zfill(4)
if(int(phigh + "0" * (dec_len-4)) * int(qhigh + "0" * (dec_len-4)) < n and int(phigh + "9" * (dec_len-4)) * int(qhigh + "9" * (dec_len-4)) > n):
break
find(phigh,qhigh,plow,qlow)
except:
pass
sound
题目：
import numpy as np
from numpy.polynomial import polynomial as poly
from Crypto.Util.number import *
# from secert import flag
def poly_mul(x, y, z, poly_mod):
init_poly = poly.polymul(x, y)
res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z
return np.int64(np.round(res_poly))
def poly_add(x, y, z, poly_mod):
init_poly = poly.polyadd(x, y)
res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z
return np.int64(np.round(res_poly))
def r2_distribution(len):
return np.random.randint(0, 2, len, dtype=np.int64)
def rz_distribution(z, len):
return np.random.randint(0, z, len, dtype=np.int64)
def gass_distribution(len):
return np.int64(np.random.normal(0, 2, size=len))
def keygen(len, z, poly_mod):
s = r2_distribution(len)
a = rz_distribution(z, len)
e = gass_distribution(len)
b = poly_add(poly_mul(-a, s, z, poly_mod), -e, z, poly_mod)
key = [a, b, s]
return key
def encrypt(key, lent, q, t, poly_mod, message):
lm = []
mg = hex(message)[2:]
for i in range(0, len(mg)):
lm.append(ord(mg[i]))
m = np.array(lm + [0] * (lent - len(lm)), dtype=np.int64) % t
delta = q // t
delta_m = delta * m % q
e1 = gass_distribution(lent)
e2 = gass_distribution(lent)
u = r2_distribution(lent)
a = key[0]
b = key[1]
c0 = poly_add(poly_add(poly_mul(b, u, q, poly_mod), e1, q, poly_mod), delta_m, q, poly_mod)
c1 = poly_add(poly_mul(a, u, q, poly_mod), e2, q, poly_mod)
c = [c0, c1]
return c
n = 128
q = 2**60
t = 2**32
poly_mod = np.array([1] + [0] * (n - 1) + [1])
key = keygen(n, q, poly_mod)
print(key)
# m = bytes_to_long("test")
# c = encrypt(key, n, q, t, poly_mod, m)
# print("c0 =", c[0].tolist())
# print("c1 =", c[1].tolist())
# print("a =", key[0].tolist())
# print("b =", key[1].tolist())
# print("s =", key[2].tolist())
'''
c0 = [561582066946621440, 817928620285456128, 42443557674760704, 394102843794633984, 72227332717773568, 670192568490572288, 1124338053013283584, 280137744525874176, 63888555088669696, 208355146401743872, 301595565562120704, 50991331858064384, 686628375362950656, 584548366308243456, 1133668516727752192, 474240047688777728, 985154171217232384, 501564712591768576, 914588095025884160, 746830802337096704, 459209143204393984, 603634479787543552, 69069089375354880, 473248420863702016, 754603248638489600, 883576336602057728, 644743636485886976, 319901457654988800, 89793303522564096, 1090071466212856832, 369690536666460160, 1082593341867948032, 441359938321465344, 496386518207440896, 863575421687413760, 811516483959451648, 205996965699836928, 170811895655694336, 335832012272743424, 402108133996681216, 222897130593269760, 317187616437233664, 202919598933315584, 750395341955145728, 366873741733378048, 117730747288055808, 298767968401977344, 923270470424109056, 1076698083295752192, 926422812303050752, 216450081157644288, 981499274968659968, 349655761329862656, 557140442005530624, 858566688669024256, 1149813151825131520, 553370166035001344, 493722732465334272, 732590954557634560, 1052906163890288640, 1021790009160361984, 796011853108049920, 978483522580508672, 894955797433884672, 203559391733489664, 1062410754780596224, 452371485913219072, 651736133029277696, 313976115776903168, 31756099628290048, 71787963926824960, 1109713454413903872, 1112298691994664960, 539132530906077184, 435437107964127232, 833705546252720128, 928849583016886272, 526205130688186368, 1121288102191632384, 536933088453670912, 924962525849556992, 241106313851269120, 717238131918897152, 452642326250387456, 354673268076457984, 16428317258336256, 1061713751710105600, 1139952509444370432, 146561032291504128, 944139817563172864, 670119880592367616, 424458702156075008, 26734611035709440, 552311974354061312, 252009367779129344, 362515232289822720, 942674829586386944, 444916638598115328, 931633333648844800, 54609902697099264, 831316650858829824, 113431421994166272, 907245098202316800, 89326594807300096, 1016570475364521984, 175954756550047744, 53317212366995456, 49595714294925312, 490302383520435200, 260454924258463744, 713597063793843200, 759813046691484672, 491213271622251520, 861532845783883776, 1001029896578621440, 1017093991719427072, 901303193624896512, 85708980918313472, 1094723859831225856, 978173121944355840, 1074912611780537344, 816683396743236608, 406912122093641728, 326181480111288320, 644075764054597632, 114416502291357696, 543109737210728448, 311623753071517696]
c1 = [91790686412574976, 744110810763883904, 864964412801026560, 548689841412167296, 740051294265845504, 57902427994320256, 1068935585666797056, 625707146907438848, 551559740589006848, 233440834921673728, 108552546335437312, 166310503165480448, 267060328550531584, 735758245725702656, 712188529675013632, 386374530222726144, 823764165634433536, 123823217368593408, 1004488834478358528, 177477850679225344, 882498511506926592, 5562190320664577, 1106414131124581376, 327516552070835200, 1028475201394497536, 847983498883162112, 1095687065391010816, 706624008349679616, 204676471898160128, 926864853752850432, 152748692869394432, 326128165710331904, 237842086203092992, 1057799799477599232, 345130623233955840, 790672249565697024, 523310000234446848, 840615312867051520, 924979087214993408, 979878291879419904, 115424422845719552, 884924921252442112, 579700963339163648, 1097673093701288960, 704450636638808064, 556078232166107136, 600772693891751936, 905676852758437888, 33621101477464064, 962348719049031680, 925511116990984192, 722520866171662336, 84706802559584256, 530104859095961600, 586276707214465024, 1037552671549552640, 47697269444673536, 210690498450145280, 65070464261654528, 550494166683250688, 777902097764929536, 490832146778818560, 229195607527737344, 767464696299196416, 237315984854040576, 836604288237121536, 507968614131243008, 1146549269233274880, 947811005289312256, 415029326696218624, 73794452197351424, 1111805188636655616, 574425125131241472, 1077883538301097984, 1093417286225403904, 860646266870226944, 238318354083344384, 200921121541777408, 896691473408880640, 794971973394204672, 128454122568243200, 1048391326124871680, 811035464481740800, 922934079239356416, 1033337101914234880, 253445566297591808, 820899412762693632, 51737950452322304, 115554283493984256, 1013231171511318528, 887144973891745792, 903483706965391360, 1100501053366775808, 691065365527990272, 265415356256839680, 969461346065672192, 719496129535698944, 177295085227089920, 860427351595780096, 125812051803891712, 852658796584968192, 487770283774704640, 1070758201904617472, 696983558330196992, 911281563710520320, 676402547272127488, 240686574930634752, 412323376183429120, 619325898981327872, 551028995171842048, 124379235049986048, 649110127901071360, 453922531021119488, 1022481642604582912, 637680606991188992, 51749356430436352, 388350126415356928, 335267552976254464, 960188628024263168, 1088514924986558976, 1094423617550431488, 451833526251570688, 870461009339176704, 697351158038040832, 536089791190207360, 1118146398557536256, 518612046112251904, 241398597936840704]
a = [219983724512243970, 752269838678521187, 480509403910281428, 133185208045420765, 490932722804543133, 372886136396692359, 354557330633882122, 678374399146208018, 960245804475102275, 806115518790255556, 828442613098615970, 544833163224524043, 101022959319030935, 117082421755238805, 461182355875216799, 1056119810024896502, 1082000166040876591, 738717114032361767, 578460771662302172, 21556920074594644, 708384954866463679, 1128876901552996333, 874708202228666633, 1092990784029535155, 705415640472089353, 29671570923717836, 386333436179138094, 279081567858606603, 358852578576320987, 847350768179480795, 817603347707592640, 378977756047386392, 201769345485693076, 1063632060034171765, 1015775208741323787, 365127265851837110, 895275437758090601, 901913451551062231, 86419657119953320, 1149882820426142461, 157964525788076127, 631235061398583563, 470949966047613817, 180994349394944987, 228238609714444899, 73624200469844200, 521149905985689963, 19697681380014322, 233461826565515880, 891353264527116993, 1132362343348330909, 719302772676639611, 816690530086729127, 612858319654028202, 1029240232500231324, 266903296429217560, 66793172770160368, 836559325488504608, 1112595888239841739, 1115401337078198049, 261716078450833148, 235662011088480216, 24855917687216082, 619578281956001818, 589359800577838713, 780827177034370452, 62331996978291742, 757201723755709445, 325754948905836705, 298782045417610682, 958766007892311371, 474147826024027639, 1070490722277174646, 190459580153148093, 575005416421018885, 1120664053122918701, 982594533717886793, 252358471190638150, 869750160966337040, 1014322228871199234, 665558545558521628, 105433885394318337, 377027901347400638, 858616841227650075, 1043520529148794434, 1011002490399424434, 207664442877510988, 871194434207030706, 43210520355326250, 602232789264907632, 474051046305769969, 184712552380050689, 795080413713622552, 69957213032924047, 528473007846250043, 169221743016746138, 455880753546244419, 329225658406843642, 1150659098485422471, 626876298585651008, 490793379497608670, 933534706184661647, 467052917787037730, 1075596724935302342, 633000416730524162, 1090163205445120705, 72568659182243843, 571233962016655997, 1038522694640247261, 1025630622605696194, 553753007953333627, 231471906689387866, 558788723869154294, 673804202648107772, 232283327890481849, 39742925179368561, 135909458983766175, 192124298319965985, 839263496419016075, 162231894553173376, 661693215639557019, 655784289160683355, 1062416543453873451, 319938129595811007, 1002025365666496902, 272017768612866462, 482130564327357100, 982163056351966292]
b = [820893636450185216, 1088723008695521024, 563505788571372160, 225792174390707712, 531991982654429312, 676436714054308864, 74314379213871872, 78960436919170688, 744901196366641920, 556510129527018752, 71967857250009600, 714820946954724352, 1047939442957058048, 475133098260006400, 764020773208596992, 495337689359947776, 969475874903125504, 132719289181729792, 301591784012423168, 886113347782835200, 477381121894258688, 843499387721308160, 508541992967101440, 135898603458110464, 373248303372987392, 696522694584843264, 22397882759483392, 867189773938512896, 231922357411858432, 452886634658905088, 337138259452950528, 246330467020038144, 336880752906045440, 712110254503864320, 1109022090563764224, 736941976050098176, 340820746543463424, 319152585759258624, 627473838419951616, 724549720670470144, 941976447076147200, 284306369459089408, 474986938990024704, 169392264058798080, 425082943668336640, 780502226419180544, 534812953559536640, 307991466712799232, 256772641512932352, 954565062645100544, 642433129475169280, 554579429440409600, 492586567437330432, 504243514518411264, 559583345168955392, 1047970717391220736, 354007966625097728, 944087368508420096, 48593600443238400, 412546108591775744, 371798716943661056, 109603610083078144, 912962403831732224, 493593202496430080, 435411737100828672, 416258656632209408, 41271759105748992, 547450588221173760, 1019985813100816384, 1133270880179824640, 416184705628168192, 1002938666972422144, 131467088438026240, 730507494540156928, 1122116292811296768, 179931222600130560, 704668788433995776, 693568343631073280, 159315312318967808, 228151058164389888, 78591434106697728, 1101441417145767936, 1011500470535821312, 103335769958184960, 723984495516817408, 421553904096403456, 1009636649059076096, 880471059436941312, 1017699541008359424, 880891531629418496, 1001214838765556736, 584549630850997248, 63724037422592000, 984435711617449984, 737723590588489728, 235901319105159168, 867142310717528064, 62598429756019712, 135623731618318336, 103508320292760576, 714343001741491200, 384031562306680832, 620521749068774400, 562199194838183936, 137440949282672640, 105902179785320448, 76984505248291840, 81968680790070272, 932887350172256256, 162426306785337344, 248707672736583680, 338911851801801216, 664174993098860032, 590418449833950720, 668934689108922112, 1050363471682760704, 627510981430159872, 157201265188110848, 332191804534742528, 610005938211220480, 789419961205813248, 350516436368000512, 135054071035246848, 1103634020293607168, 851221988945015936, 339941701245870080, 810615510791110656, 1139102409849577472]
s = [0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0]
'''
分析
已知如下基本信息，我们对其中的函数进行详细分析：
- x、y：多项式系数列表
- z：模数
- poly_mod：模多项式系数列表
def poly_mul(x, y, z, poly_mod):
init_poly = poly.polymul(x, y)
res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z
return np.int64(np.round(res_poly))
#具体来说，该函数实现x、y多项式相乘后，每项系数模z，再将整个多项式模poly_mod，也就是这道题的基础算式。
# poly_add函数则是跟poly_mul完全一样，不做赘述。
def r2_distribution(len):
return np.random.randint(0, 2, len, dtype=np.int64)
#该函数生成一个长度为len，元素为0或1的随机数列表
def rz_distribution(z, len):
return np.random.randint(0, z, len, dtype=np.int64)
#该函数生成一个长度为len，元素为0-z之间的随机数列表
def gass_distribution(len):
return np.int64(np.random.normal(0, 2, size=len))
#该函数返回一个长度为len，随机数从给定正态分布中抽取的列表，各个参数意义详见：
自己测试一下就可以知道，其实可以认为他就是一个小噪声，即小干扰：
length = 128
print(gass_distribution(length))
[-1 0 -1 2 0 1 2 1 0 0 0 0 1 -4 0 0 -1 3 2 -1 -1 2 0 0 -1 3 2 1 0 1 0 -2 -2 3 -1 3 -4 -1 -1 0 1 0 -3 -3 2 2 0 -4 0 0 0 0 0 -1 -1 -1 0 -2 0 0 -2 0 0 0 1 -1 0 0 -2 2 0 1 -1 2 2 -3 0 -1 3 1 -2 -2 0 0 0 -1 4 2 2 -1 0 -1 4 -1 1 0 0 -1 -1 0 0 3 0 1 -3 -1 0 -1 1 2 0 1 -1 -1 -2 -1 0 -1 -1 1 2 0 3 -1 1 0 -2 1]
以上就是五个加密需要用到的基本函数，总结一下，其实他就是定义了一个多项式的商环，运算也均在这个商环上进行。而这些随机生成的列表，也就可以看作是这个商环上的多项式系数列表，这个商环如下：
$$
Fq[x]=Zq[x]/f(x)
$$
其中，f(x)就是题目中的poly_mod，Zq[x]指模q下的多项式环，请记住这个环。
再看keygen函数，就可以知道几个多项式的关系：
$$
b(x) = -s(x)a(x)-e(x)
$$
其中，s的系数均为0或1，e的系数为一个正态分布的小噪声，而a、b的系数则应该是由较大的数构成的。
然后对于encrypt函数，其加密流程如下：
- 把flag转为十六进制字符串，然后把每个十六进制字符转为ASCII码，然后在后面填充足够的0使得m也是一个同长度的多项式系数列表(这些东西自己生成数据测试一下就明白了)
- 定义一个较大的数delta，题目中是2^28，然后将m的多项式系数乘delta。这里就可以想到，对于m来说，只有前面非0的部分乘上了delta而显著变大，后面的填充0是不变的
- 生成两个满足正态分布的小噪声e1、e2，再生成一个系数均为0或1的随机临时密钥u，计算下面两个多项式作为密文并返回(其中dm表示乘上了delta的m系数列表)：
$$
c0(x)=b(x)u(x)+e1(x)+dm(x)
$$
$$
c1(x)=a(x)u(x)+e2(x)
$$
那么加密流程就分析完了，接下来进入解密。
解密
其实见过的话，差不多就能反应过来这其实是RLWE加密，而题目实现的其实就是RLWE的标准加密过程，具体可以参考：
格密码之Ring-LWE (section 1) - 知乎 (zhihu.com)
了解了加解密流程的话，会发现其实这个题目已经给好了我们私钥s，而有了私钥s我们就可以用如下方式解密(为了表示方便，多项式后面就不写(x)了)：
由于有：
$$
b=-as+e
$$
所以：
$$
bu=-asu+eu
$$
$$
c0+s*c1=(bu+e1+dm)+s(au+e2)=-asu+eu+e1+dm+asu+se2=dm+(eu+e1+se2)
$$
也就是：
$$
c0+sc1=dm+(eu+el+se2)
$$
可以发现，后面的(eu+e1+se2)仍然是个小噪声，因此我们直接对(c0 + s c1)模delta，就能得到m。然后有一点需要注意，噪声(eu+e1+se2)可能有负值，而为负值的时候，模delta会导致最终结果小1，需要对应添加回去。
exp：
import numpy as np
from numpy.polynomial import polynomial as poly
from Crypto.Util.number import *
# from secert import flag
def poly_mul(x, y, z, poly_mod):
init_poly = poly.polymul(x, y)
res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z
return np.int64(np.round(res_poly))
def poly_add(x, y, z, poly_mod):
init_poly = poly.polyadd(x, y)
res_poly = poly.polydiv(init_poly % z, poly_mod)[1] % z
return np.int64(np.round(res_poly))
def r2_distribution(len):
return np.random.randint(0, 2, len, dtype=np.int64)
def rz_distribution(z, len):
return np.random.randint(0, z, len, dtype=np.int64)
def gass_distribution(len):
return np.int64(np.random.normal(0, 2, size=len))
def keygen(len, z, poly_mod):
s = r2_distribution(len)
a = rz_distribution(z, len)
e = gass_distribution(len)
b = poly_add(poly_mul(-a, s, z, poly_mod), -e, z, poly_mod)
key = [a, b, s]
return key
def encrypt(key, lent, q, t, poly_mod, message):
lm = []
mg = hex(message)[2:]
for i in range(0, len(mg)):
lm.append(ord(mg[i]))
m = np.array(lm + [0] * (lent - len(lm)), dtype=np.int64) % t
delta = q // t
delta_m = delta * m % q
e1 = gass_distribution(lent)
e2 = gass_distribution(lent)
u = r2_distribution(lent)
a = key[0]
b = key[1]
c0 = poly_add(poly_add(poly_mul(b, u, q, poly_mod), e1, q, poly_mod), delta_m, q, poly_mod)
c1 = poly_add(poly_mul(a, u, q, poly_mod), e2, q, poly_mod)
c = [c0, c1]
return c
n = 128
q = 2**60
t = 2**32
poly_mod = np.array([1] + [0] * (n - 1) + [1])
c0 = [561582066946621440, 817928620285456128, 42443557674760704, 394102843794633984, 72227332717773568, 670192568490572288, 1124338053013283584, 280137744525874176, 63888555088669696, 208355146401743872, 301595565562120704, 50991331858064384, 686628375362950656, 584548366308243456, 1133668516727752192, 474240047688777728, 985154171217232384, 501564712591768576, 914588095025884160, 746830802337096704, 459209143204393984, 603634479787543552, 69069089375354880, 473248420863702016, 754603248638489600, 883576336602057728, 644743636485886976, 319901457654988800, 89793303522564096, 1090071466212856832, 369690536666460160, 1082593341867948032, 441359938321465344, 496386518207440896, 863575421687413760, 811516483959451648, 205996965699836928, 170811895655694336, 335832012272743424, 402108133996681216, 222897130593269760, 317187616437233664, 202919598933315584, 750395341955145728, 366873741733378048, 117730747288055808, 298767968401977344, 923270470424109056, 1076698083295752192, 926422812303050752, 216450081157644288, 981499274968659968, 349655761329862656, 557140442005530624, 858566688669024256, 1149813151825131520, 553370166035001344, 493722732465334272, 732590954557634560, 1052906163890288640, 1021790009160361984, 796011853108049920, 978483522580508672, 894955797433884672, 203559391733489664, 1062410754780596224, 452371485913219072, 651736133029277696, 313976115776903168, 31756099628290048, 71787963926824960, 1109713454413903872, 1112298691994664960, 539132530906077184, 435437107964127232, 833705546252720128, 928849583016886272, 526205130688186368, 1121288102191632384, 536933088453670912, 924962525849556992, 241106313851269120, 717238131918897152, 452642326250387456, 354673268076457984, 16428317258336256, 1061713751710105600, 1139952509444370432, 146561032291504128, 944139817563172864, 670119880592367616, 424458702156075008, 26734611035709440, 552311974354061312, 252009367779129344, 362515232289822720, 942674829586386944, 444916638598115328, 931633333648844800, 54609902697099264, 831316650858829824, 113431421994166272, 907245098202316800, 89326594807300096, 1016570475364521984, 175954756550047744, 53317212366995456, 49595714294925312, 490302383520435200, 260454924258463744, 713597063793843200, 759813046691484672, 491213271622251520, 861532845783883776, 1001029896578621440, 1017093991719427072, 901303193624896512, 85708980918313472, 1094723859831225856, 978173121944355840, 1074912611780537344, 816683396743236608, 406912122093641728, 326181480111288320, 644075764054597632, 114416502291357696, 543109737210728448, 311623753071517696]
c1 = [91790686412574976, 744110810763883904, 864964412801026560, 548689841412167296, 740051294265845504, 57902427994320256, 1068935585666797056, 625707146907438848, 551559740589006848, 233440834921673728, 108552546335437312, 166310503165480448, 267060328550531584, 735758245725702656, 712188529675013632, 386374530222726144, 823764165634433536, 123823217368593408, 1004488834478358528, 177477850679225344, 882498511506926592, 5562190320664577, 1106414131124581376, 327516552070835200, 1028475201394497536, 847983498883162112, 1095687065391010816, 706624008349679616, 204676471898160128, 926864853752850432, 152748692869394432, 326128165710331904, 237842086203092992, 1057799799477599232, 345130623233955840, 790672249565697024, 523310000234446848, 840615312867051520, 924979087214993408, 979878291879419904, 115424422845719552, 884924921252442112, 579700963339163648, 1097673093701288960, 704450636638808064, 556078232166107136, 600772693891751936, 905676852758437888, 33621101477464064, 962348719049031680, 925511116990984192, 722520866171662336, 84706802559584256, 530104859095961600, 586276707214465024, 1037552671549552640, 47697269444673536, 210690498450145280, 65070464261654528, 550494166683250688, 777902097764929536, 490832146778818560, 229195607527737344, 767464696299196416, 237315984854040576, 836604288237121536, 507968614131243008, 1146549269233274880, 947811005289312256, 415029326696218624, 73794452197351424, 1111805188636655616, 574425125131241472, 1077883538301097984, 1093417286225403904, 860646266870226944, 238318354083344384, 200921121541777408, 896691473408880640, 794971973394204672, 128454122568243200, 1048391326124871680, 811035464481740800, 922934079239356416, 1033337101914234880, 253445566297591808, 820899412762693632, 51737950452322304, 115554283493984256, 1013231171511318528, 887144973891745792, 903483706965391360, 1100501053366775808, 691065365527990272, 265415356256839680, 969461346065672192, 719496129535698944, 177295085227089920, 860427351595780096, 125812051803891712, 852658796584968192, 487770283774704640, 1070758201904617472, 696983558330196992, 911281563710520320, 676402547272127488, 240686574930634752, 412323376183429120, 619325898981327872, 551028995171842048, 124379235049986048, 649110127901071360, 453922531021119488, 1022481642604582912, 637680606991188992, 51749356430436352, 388350126415356928, 335267552976254464, 960188628024263168, 1088514924986558976, 1094423617550431488, 451833526251570688, 870461009339176704, 697351158038040832, 536089791190207360, 1118146398557536256, 518612046112251904, 241398597936840704]
a = [219983724512243970, 752269838678521187, 480509403910281428, 133185208045420765, 490932722804543133, 372886136396692359, 354557330633882122, 678374399146208018, 960245804475102275, 806115518790255556, 828442613098615970, 544833163224524043, 101022959319030935, 117082421755238805, 461182355875216799, 1056119810024896502, 1082000166040876591, 738717114032361767, 578460771662302172, 21556920074594644, 708384954866463679, 1128876901552996333, 874708202228666633, 1092990784029535155, 705415640472089353, 29671570923717836, 386333436179138094, 279081567858606603, 358852578576320987, 847350768179480795, 817603347707592640, 378977756047386392, 201769345485693076, 1063632060034171765, 1015775208741323787, 365127265851837110, 895275437758090601, 901913451551062231, 86419657119953320, 1149882820426142461, 157964525788076127, 631235061398583563, 470949966047613817, 180994349394944987, 228238609714444899, 73624200469844200, 521149905985689963, 19697681380014322, 233461826565515880, 891353264527116993, 1132362343348330909, 719302772676639611, 816690530086729127, 612858319654028202, 1029240232500231324, 266903296429217560, 66793172770160368, 836559325488504608, 1112595888239841739, 1115401337078198049, 261716078450833148, 235662011088480216, 24855917687216082, 619578281956001818, 589359800577838713, 780827177034370452, 62331996978291742, 757201723755709445, 325754948905836705, 298782045417610682, 958766007892311371, 474147826024027639, 1070490722277174646, 190459580153148093, 575005416421018885, 1120664053122918701, 982594533717886793, 252358471190638150, 869750160966337040, 1014322228871199234, 665558545558521628, 105433885394318337, 377027901347400638, 858616841227650075, 1043520529148794434, 1011002490399424434, 207664442877510988, 871194434207030706, 43210520355326250, 602232789264907632, 474051046305769969, 184712552380050689, 795080413713622552, 69957213032924047, 528473007846250043, 169221743016746138, 455880753546244419, 329225658406843642, 1150659098485422471, 626876298585651008, 490793379497608670, 933534706184661647, 467052917787037730, 1075596724935302342, 633000416730524162, 1090163205445120705, 72568659182243843, 571233962016655997, 1038522694640247261, 1025630622605696194, 553753007953333627, 231471906689387866, 558788723869154294, 673804202648107772, 232283327890481849, 39742925179368561, 135909458983766175, 192124298319965985, 839263496419016075, 162231894553173376, 661693215639557019, 655784289160683355, 1062416543453873451, 319938129595811007, 1002025365666496902, 272017768612866462, 482130564327357100, 982163056351966292]
b = [820893636450185216, 1088723008695521024, 563505788571372160, 225792174390707712, 531991982654429312, 676436714054308864, 74314379213871872, 78960436919170688, 744901196366641920, 556510129527018752, 71967857250009600, 714820946954724352, 1047939442957058048, 475133098260006400, 764020773208596992, 495337689359947776, 969475874903125504, 132719289181729792, 301591784012423168, 886113347782835200, 477381121894258688, 843499387721308160, 508541992967101440, 135898603458110464, 373248303372987392, 696522694584843264, 22397882759483392, 867189773938512896, 231922357411858432, 452886634658905088, 337138259452950528, 246330467020038144, 336880752906045440, 712110254503864320, 1109022090563764224, 736941976050098176, 340820746543463424, 319152585759258624, 627473838419951616, 724549720670470144, 941976447076147200, 284306369459089408, 474986938990024704, 169392264058798080, 425082943668336640, 780502226419180544, 534812953559536640, 307991466712799232, 256772641512932352, 954565062645100544, 642433129475169280, 554579429440409600, 492586567437330432, 504243514518411264, 559583345168955392, 1047970717391220736, 354007966625097728, 944087368508420096, 48593600443238400, 412546108591775744, 371798716943661056, 109603610083078144, 912962403831732224, 493593202496430080, 435411737100828672, 416258656632209408, 41271759105748992, 547450588221173760, 1019985813100816384, 1133270880179824640, 416184705628168192, 1002938666972422144, 131467088438026240, 730507494540156928, 1122116292811296768, 179931222600130560, 704668788433995776, 693568343631073280, 159315312318967808, 228151058164389888, 78591434106697728, 1101441417145767936, 1011500470535821312, 103335769958184960, 723984495516817408, 421553904096403456, 1009636649059076096, 880471059436941312, 1017699541008359424, 880891531629418496, 1001214838765556736, 584549630850997248, 63724037422592000, 984435711617449984, 737723590588489728, 235901319105159168, 867142310717528064, 62598429756019712, 135623731618318336, 103508320292760576, 714343001741491200, 384031562306680832, 620521749068774400, 562199194838183936, 137440949282672640, 105902179785320448, 76984505248291840, 81968680790070272, 932887350172256256, 162426306785337344, 248707672736583680, 338911851801801216, 664174993098860032, 590418449833950720, 668934689108922112, 1050363471682760704, 627510981430159872, 157201265188110848, 332191804534742528, 610005938211220480, 789419961205813248, 350516436368000512, 135054071035246848, 1103634020293607168, 851221988945015936, 339941701245870080, 810615510791110656, 1139102409849577472]
s = [0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0]
_c1 = [0 for i in range(len(c1))]
for i in range(len(c1)):
_c1[i] = (q - c1[i]) % q
final = poly_add(c0 , poly_mul(s, c1, q, poly_mod), q, poly_mod)
temp = (final//(2**28))[:76]
temp1 = (final%(2**28))[:76]
c = ""
for i in range(len(temp)):
if(temp1[i] > 100000):
c += chr(temp[i]+1)
else:
c += chr(temp[i])
print(long_to_bytes(int(c,16)))
这道属于后量子密码，当时看着也蒙了，RLWE加密让人措不及防，一下子是真没想起来，后面去复现才发现的，很可惜。这种题型有个很明显的特征，就是长，把该有的、不该有的都写了上去，比如此题的poly_add。尤其是分组密码中，有些对AES的改编S盒或列混淆等步骤时的改编，从而写出一大段。要求我们的算法敏感性和代码理解能力，并转换为我们所学的知识，如果是未学，那就现学现卖，或者跟我一起坐牢吧。
知识总结
1.
至今为止已知m数值转flag有2种方法（一种不行就试另一种）:
1.转字节
2.转ascii码（在m长度不大的情况下，就如本题，既然能转ascii码，那么大胆猜测还有一种可能是能按照26个英文字母进行转换，前提也是m长度不大）
这里简单说一下16进制转字符串，十六进制数的一个基本特点：它由十六个数码：数字0～9加上字母A-F组成，所以说纯数字转字符串一般不考虑16进制转化
2.
< a >
已知 n , phi 如何求p，q（注：n = p * q , phi = (p-1) * (q-1)）：
两个方程，两个未知数，很容易解：
告诉了我们 n = p * q , phi = (p-1) * (q-1) = p * q - (p+q) + 1 = n - (p+q) + 1
==>n = p * q , phi = n - (p+q) + 1
==>p + q = n - phi + 1
==>(p - q)^2 = (p+q)^2 - 4 * n
==>p - q = [(p-q)^2] ^0.5
==>p = [(p + q) + (p - q)] // 2
==>q = (p + q) - p
p_q = n - phi + 1 # p_q = p + q
p_q_2 = p_q**2 - 4*n # p_q_2 = (p - q)^2
p_q_1 = gmpy2.iroot(p_q_2,2)[0] # p_q_1 = p - q
p = (p_q + p_q_1) // 2
q = p_q - p
< b >
已知 n，e * d ，如何求 p，q（注：n = p q，e d = 1 mod phi）:
此时已知的是 n = p * q , e * d = 1 mod phi,那么我们便将已知转化为 n，phi
==>e * d - 1 = k * phi = k * (p - 1) * (q-1)
==> k = (e * d - 1) // [p * q - (p + q) + 1] > (e * d - 1) // p * q
k = ((e * d-1) // n)+1
phi = (e * d- 1) // kk的详细解析:
这里不等式两边的分母一个pq，一个pq-(p+q)+1相差并不大，并且还是整除，所以估计(ed-1)//pq和(ed-1)//(pq-(p+q)+1)差值不到1用:
k = ((e * d-1) // n)+1
phi = (e * d- 1) // k
然后这里两次整除后，后面小数部分应该都省略掉了
转载
分享
发布投稿
优秀作者
没有评论