【浅谈系列】Benaloh cryptosystem

5 minute read

Published:

最近连续两次在 CTF 里看到 Benaloh cryptosystem,学习后简单记录一下。

最近连续两次在 CTF 里看到 Benaloh cryptosystem,学习后简单记录一下。

1. Higher residuosity problem

  • 建议参考:

wikipedia - Higher residuosity problem

它的定义 wikipedia 已经说的很清楚了。

至于如何解任意次剩余,可以参考我的另一篇博文:浅谈高次剩余的求解

2. Benaloh cryptosystem

  • 建议参考:

(1) wikipedia - Benaloh cryptosystem

(2) Benaloh’s Dense Probabilistic Encryption Revisited

(1) 密钥生成

(2) 加密解密

(3) 安全性

它的安全性依赖 Higher residuosity problem

具体来说,就是对于 $x^m = a \pmod n$,如果不能分解 n,则无法解这个 m 次剩余。

3. DiceCTF 2021 benaloh

这题出题的思路参考了CONFidence CTF 2015 - RSA1

主要考点是 Gröbner basisBenaloh cryptosystem

(1) 思路

看代码显然是 Benaloh cryptosystem。但与一般形式不同的是,它把原本的 $y^m u^r$ 中的 $u$ 从随机数改成了一个 LCG

而由于我们已知 flag 的前几个字母必然是 dice{,因此可以建立方程组如下,然后利用 Gröbner basis 方法解出 LCG的参数,从而还原 flag

\[\begin{cases} v_1 \equiv u^17 \\ v_2 \equiv (au+c)^17 \\ v_3 \equiv [a^2u+c(a+1)]^17 \\ ... \\ v_10 = [a^9u+c(a^8+...+a+1)]^17 \end{cases} \pmod n\]

(2) Gröbner basis 简述

(3) 代码实现

代码如下:

r = 17

with open('out.txt') as f:
	n, y = eval(f.readline())
	R = Integers(n)
	z = list(map(R, f.readlines()))

y = R(y)
log = {y^i: f'{i:x}' for i in range(r)}

P.<u, a, c> = PolynomialRing(R)

G = []
f = u
for i, m in enumerate(b'di'.hex()):
	G.append(f^r - z[i]/y^int(m, 16))
	f = a*f + c

B = Ideal(G).groebner_basis()
print(B)

flag = ''
f = -B[1].monomial_coefficient(c)*c
for i in range(len(z)):
	flag += log[z[i]/(f.monomial_coefficient(c)^r*-B[0].constant_coefficient())]
	f = -B[2].constant_coefficient()*f + c
print(bytes.fromhex(flag))

结果如下:

4. D3CTF 2021 simpleGroup

(1) 思路概述

看代码,显然是标准的 Benaloh cryptosystem

对照 Benaloh cryptosystem的论文,代码中的参数设置看不出有什么问题。

而我们已知这个系统的安全性是基于 Higher residuosity problem

The security of this scheme rests on the Higher residuosity problem.
Specifically, given z,r and n where the factorization of n is unknown, 
it is computationally infeasible to determine whether z is an rth residue mod n.

再加上之前的一题 babylattice 和这题用的 n 相同,这显然是暗示我们需要利用第一题的条件来分解 n

所以需要首先构造格来分解 n,再用 Benaloh cryptosystem 的解密过程,即可得到 flag

(2) 第一步:分解 n

怎么构造格来分解 n 呢?在前一个问题 babylattice 中给出了条件和提示。

\[\begin{array}{} a_{12} \cdot b - a_{11} = k_1p \\ a_{22} \cdot b - a_{21} = k_2q \end{array} \Rightarrow a_{12}a_{22}b^2 - b(a_{12}a_{21} + a_{11}a_{22}) + a_{11}a_{21} = k_1k_2pq\]

不妨设 $K = k_1k_2,n = pq$,则有:

\[a_{12}a_{22}b^2 - b(a_{12}a_{21} + a_{11}a_{22}) - Kn = -a_{11}a_{21}\]

据此构造格:

\[(a_{12}a_{22}, -(a_{12}a_{21}+a_{11}a_{22}), -K) \begin{pmatrix} 1&0&b^2\\ 0&-1&b\\ 0&0&n \end{pmatrix} = (a_{12}a_{22}, a_{12}a_{21}+a_{11}a_{22}, -a_{11}a_{21})\]

分解可得四个素数,而后因为 $gcd(a_{12} \cdot b - a_{11} , n) = p$,利用 gcd 即可分解 n

代码如下:

n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
b = 65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196

v1 = vector(ZZ, [1, 0, b^2])
v2 = vector(ZZ, [0, -1, b])
v3 = vector(ZZ, [0, 0, n])
lattice = matrix([v1,v2,v3])

tmp = [abs(i) for i in lattice.LLL()[0]]

list_1 = [int(i) for i in str(factor(tmp[0])).split("*")]
list_2 = [int(i) for i in str(factor(tmp[-1])).split("*")]

p = gcd(list_1[0]*b - list_2[0], n)
if p == 1:
    p = gcd(list_1[0]*b - list_2[1], n)
q = n // p

print("p =", p)
print("q =", q)
print("p*q == n?", p*q == n)

结果如下:

(3) 第二步:Benaloh cryptosystem decryption

参照 wikipedia 里给出的解密步骤来即可。

步骤如下:

得到 a 之后,我们需要解 $x^m = a \pmod n$,此题中也就是 $c^{\phi / e} = y^{m \cdot \phi / e} \pmod n$。

两种方法,exhaustive search 或是 BSGS。如果e比较小,我们可以直接 exhaustive search。这里的 e还是有点大,所以我们选择大小步。

代码如下:

from Crypto.Util.number import long_to_bytes
from tqdm import tqdm

n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
y = 12064801545723347322936991186738560311049061235541031580807549422258814170771738262264930441670708308259694588963224372530498305648578520552038029773849342206125074212912788823834152785756697757209804475031974445963691941515756901268376267360542656449669715367587909233618109269372332127072063171947435639328
e = 1928983487
C = [63173987757788284988620600191109581820396865828379773315280703314093571300861961873159324234626635582246705378908610341772657840682572386153960342976445563045427986000105931341168525422286612417662391801508953619857648844420751306271090777865836201978470895906780036112804110135446130976275516908136806153488, 9763526786754236516067080717710975805995955013877681492195771779269768465872108434027813610978940562101906769209984501196515248675767910499405415921162131390513502065270491854965819776080041506584540996447044249409209699608342257964093713589580983775580171905489797513718769578177025063630080394722500351718, 37602000735227732258462226884765737048138920479521815995321941033382094711120810035265327876995207117707635304728511052367297062940325564085193593024741832905771507189762521426736369667607865137900432117426385504101413622851293642219573920971637080154905579082646915297543490131171875075081464735374022745371, 1072671768043618032698040622345664216689606325179075270470875647188092538287671951027561894188700732117175202207361845034630743422559130952899064461493359903596018309221581071025635286144053941851624510600383725195476917014535032481197737938329722082022363122585603600777143850326268988298415885565240343957, 27796821408982345007197248748277202310092789604135169328103109167649193262824176309353412519763498156841477483757818317945381469765077400076181689745139555466187324921460327576193198145058918081061285618767976454153221256648341316332169223400180283361166887912012807743326710962143011946929516083281306203120, 27578857139265869760149251280906035333246393024444009493717159606257881466594628022512140403127178174789296810502616834123420723261733024810610501421455454191654733275226507268803879479462533730695515454997186867769363797096196096976825300792616487723840475500246639213793315097434400920355043141319680299224, 29771574667682104634602808909981269404867338382394257360936831559517858873826664867201410081659799334286847985842898792091629138292008512383903137248343194156307703071975381090326280520578349920827357328925184297610245746674712939135025013001878893129144027068837197196517160934998930493581708256039240833145, 33576194603243117173665354646070700520263517823066685882273435337247665798346350495639466826097821472152582124503891668755684596123245873216775681469053052037610568862670212856073776960384038120245095140019195900547005026888186973915360493993404372991791346105083429461661784366706770467146420310246467262823, 5843375768465467361166168452576092245582688894123491517095586796557653258335684018047406320846455642101431751502161722135934408574660609773328141061123577914919960794180555848119813522996120885320995386856042271846703291295871836092712205058173403525430851695443361660808933971009396237274706384697230238104, 61258574367240969784057122450219123953816453759807167817741267194076389100252707986788076240792732730306129067314036402554937862139293741371969020708475839483175856346263848768229357814022084723576192520349994310793246498385086373753553311071932502861084141758640546428958475211765697766922596613007928849964, 13558124437758868592198924133563305430225927636261069774349770018130041045454468021737709434182703704611453555980636131119350668691330635012675418568518296882257236341035371057355328669188453984172750580977924222375208440790994249194313841200024395796760938258751149376135149958855550611392962977597279393428]

p = 7669036313101194621345265255994200133006921565596653797956940811601516306410232120057637504305295677357422367597831138570269733177579895994340511712373309
q = 9102122415165681824420871673621781250311822805618731863628192549895693024247220594372897360668046264863189831887100676431439200352775676467952192600956629

phi = (p-1) * (q-1)
tmp = phi // e

bounds = (1, e)
F = IntegerModRing(n)
result = []

x = F(pow(y, tmp, n))

for c in tqdm(C):
    a = F(pow(c, tmp, n))
    result.append(bsgs(x, a, bounds))

flag = 0
for i in result[::-1]:
    flag = flag*e + i
flag = long_to_bytes(flag)

print(flag)

结果如下:

(4) 第二步:另一种方法

此外,这篇文章的第二步用了另一种方法。

思想如下:

\[m = i \cdot e_1 + j \\ c \equiv y^{j} \cdot (y^{i} \cdot r^{e_2})^{e_1} \ (mod \ p) \\ c’ \equiv c \cdot y^{-j} \equiv (y_i \cdot r^{e_2})^{e_1} \ (mod \ p)\]

所以遍历 j 判断是否为 e1 次剩余来确定 j,也就是 m % e1

同理可得 m % e2,然后 CRT 可得 m

代码如下:

from Crypto.Util.number import *
import gmpy2

p = 7669036313101194621345265255994200133006921565596653797956940811601516306410232120057637504305295677357422367597831138570269733177579895994340511712373309
q = 9102122415165681824420871673621781250311822805618731863628192549895693024247220594372897360668046264863189831887100676431439200352775676467952192600956629
n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
y = 12064801545723347322936991186738560311049061235541031580807549422258814170771738262264930441670708308259694588963224372530498305648578520552038029773849342206125074212912788823834152785756697757209804475031974445963691941515756901268376267360542656449669715367587909233618109269372332127072063171947435639328
e = 1928983487
e1 = 36493
e2 = 52859

def GCRT(mi, ai):
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c // d * gmpy2.invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
        cura %= curm
    return (cura % curm, curm) 

def check(d,p,n):
    if((p - 1) % n == 0):
        return pow(d,(p - 1) // n,p) == 1
    else:
        k = gmpy2.gcd(n, p - 1)
        return pow(d,(p - 1) // k,p) == 1

def getM(c,e,p):
    for i in range(2,e):
        tmpc = (c * gmpy2.invert(pow(y,i,p),p)) % p
        if check(tmpc,p,e):
            return i
    exit(0)

C = [63173987757788284988620600191109581820396865828379773315280703314093571300861961873159324234626635582246705378908610341772657840682572386153960342976445563045427986000105931341168525422286612417662391801508953619857648844420751306271090777865836201978470895906780036112804110135446130976275516908136806153488, 9763526786754236516067080717710975805995955013877681492195771779269768465872108434027813610978940562101906769209984501196515248675767910499405415921162131390513502065270491854965819776080041506584540996447044249409209699608342257964093713589580983775580171905489797513718769578177025063630080394722500351718, 37602000735227732258462226884765737048138920479521815995321941033382094711120810035265327876995207117707635304728511052367297062940325564085193593024741832905771507189762521426736369667607865137900432117426385504101413622851293642219573920971637080154905579082646915297543490131171875075081464735374022745371, 1072671768043618032698040622345664216689606325179075270470875647188092538287671951027561894188700732117175202207361845034630743422559130952899064461493359903596018309221581071025635286144053941851624510600383725195476917014535032481197737938329722082022363122585603600777143850326268988298415885565240343957, 27796821408982345007197248748277202310092789604135169328103109167649193262824176309353412519763498156841477483757818317945381469765077400076181689745139555466187324921460327576193198145058918081061285618767976454153221256648341316332169223400180283361166887912012807743326710962143011946929516083281306203120, 27578857139265869760149251280906035333246393024444009493717159606257881466594628022512140403127178174789296810502616834123420723261733024810610501421455454191654733275226507268803879479462533730695515454997186867769363797096196096976825300792616487723840475500246639213793315097434400920355043141319680299224, 29771574667682104634602808909981269404867338382394257360936831559517858873826664867201410081659799334286847985842898792091629138292008512383903137248343194156307703071975381090326280520578349920827357328925184297610245746674712939135025013001878893129144027068837197196517160934998930493581708256039240833145, 33576194603243117173665354646070700520263517823066685882273435337247665798346350495639466826097821472152582124503891668755684596123245873216775681469053052037610568862670212856073776960384038120245095140019195900547005026888186973915360493993404372991791346105083429461661784366706770467146420310246467262823, 5843375768465467361166168452576092245582688894123491517095586796557653258335684018047406320846455642101431751502161722135934408574660609773328141061123577914919960794180555848119813522996120885320995386856042271846703291295871836092712205058173403525430851695443361660808933971009396237274706384697230238104, 61258574367240969784057122450219123953816453759807167817741267194076389100252707986788076240792732730306129067314036402554937862139293741371969020708475839483175856346263848768229357814022084723576192520349994310793246498385086373753553311071932502861084141758640546428958475211765697766922596613007928849964, 13558124437758868592198924133563305430225927636261069774349770018130041045454468021737709434182703704611453555980636131119350668691330635012675418568518296882257236341035371057355328669188453984172750580977924222375208440790994249194313841200024395796760938258751149376135149958855550611392962977597279393428]
m = 0
for c in C[::-1]:
    cp = c % p
    cq = c % q
    m1 = getM(cp,e1,p)
    m2 = getM(cq,e2,q)
    mm,lcm = GCRT([e1,e2],[m1,m2])
    print("Get mm: " + hex(mm))
    m *= e
    m += mm

flag = long_to_bytes(m)
print(flag)

声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.