Schmidt-Samoa 密码体系

Ruan Xingzhi -

　　2005年，Katja Schmidt-Samoa 创建了 Schmidt-Samoa 公钥密码体系。论文如下：A New Rabin-type Trapdoor Permutation Equivalent to Factoring and Its Applications

　　与 Rabin 类似，它的安全性基于大整数分解的困难性。但 Rabin 解密时会得到四个解，而 Schmidt-Samor 得到的是唯一解。

构建密钥

　　选取大整数 $p, q$, 计算 $N = p^2\cdot q$ 作为公钥。

　　计算 $d = \text{inv}(N, \varphi(pq))$ 作为私钥。

加密过程

　　对于小于 $pq$ 的明文 $m$，计算 $c = m ^ N \bmod N$ 作为密文。

解密过程

　　对于密文 $c$，计算 $c^d \bmod pq$ ，得到密文。我们接下来给出证明。

　　首先，我们计算 $\varphi(N)$. 由欧拉函数的性质，显然有 $$\varphi(N) = \varphi(p^2q) = p(p-1)(q-1)$$于是 $$x^{p(p-1)(q-1)} \equiv 1 \pmod N$$

　　尽管公钥、私钥都不包含 $pq$，但我们可以通过 $(N,d)$ 推出 $pq$. 有 $$N\cdot d \equiv 1 \pmod {(p-1)(q-1)}$$现在随便选一个数2，来考察 $2^{N\cdot d}$ 在模 $pq$ 时的表现。有$$2 ^ {N\cdot d} \equiv 2^{ N\cdot d \bmod [(p-1)(q-1)] } \equiv 2\pmod {pq}$$从而 $pq \mid 2 ^ {N\cdot d} - 2$. 于是计算$$\gcd(2 ^ {N\cdot d}-2, N)$$即可得到 $pq$. 容易发现，这里的幂可以在模 $N$ 意义下计算，以节省复杂度。现在 $pq$ 到手，我们在模 $pq$ 意义下计算 $c ^ {d}$，即$$c ^ {d} \equiv m ^ {N\cdot d} \equiv m ^ {N \cdot d \bmod (p-1)(q-1)} \equiv m \pmod{pq}$$至此完成解密。

例题

BUUCTF: [GUET-CTF2019]Uncle Sam

【附件】

　　给定了公钥、私钥，但是这个私钥 $d$ 是 $N$ 在模 $\text{lcm}(p-1, q-1)$ 下的逆元。不过没有关系，可以证明仍然有极大概率 $$2 ^ {N \cdot d} \equiv 2 \pmod {pq}$$因为  $\text{lcm}(p-1, q-1)$ 已经是 $(p-1)(q-1)$ 非常大的因子，由拉格朗日定理，2生成的子群的阶应该是 $(p-1)(q-1)$ 的因数，所以概率还是挺高的。脚本如下：

import gmpy2
from Crypto.Util.number import long_to_bytes

def getPQ(pub, priv):
    return gmpy2.gcd(pub, gmpy2.powmod(2, pub*priv, pub)-2)

def decrypt(pub, priv, enc):
    return gmpy2.powmod(enc, priv, getPQ(pub, priv))

pubkey =  2188967977749378274223515689363599801320698247938997135947965550196681836543275429767581633044354412195352229175764784503562989045268075431206876726265968368605210824232207290410773979606662689866265612797103853982014198455433380266671856355564273196151136025319624636805659505233975208570409914054916955097594873702395812044506205943671404203774360656553350987491558491176962018842708476009578127303566834534914605109859995649555122751891647040448980718882755855420324482466559223748065037520788159654436293431470164057490350841209872489538460060216015196875136927502162027562546316560342464968237957692873588796640619530455268367136243313422579857823529592167101260779382665832380054690727358197646512896661216090677033395209196007249594394515130315041760988292009930675192749010228592156047159029095406021812884258810889225617544404799863903982758961208187042972047819358256866346758337277473016068375206319837317222523597
privkey = 1430375790065574721602196196929651174572674429040725535698217207301881161695296519567051246290199551982286327831985649037584885137134580625982555634409225551121712376849579015320947279716204424716566222721338735256648873164510429206991141648646869378141312253135997851908862030990576004173514556541317395106924370019574216894560447817319669690140544728277302043783163888037836675290468320723215759693903569878293475447370766682477726453262771004872749335257953507469109966448126634101604029506006038527612917418016783711729800719387298398848370079742790126047329182349899824258355003200173612567191747851669220766603
enc = 1491421391364871767357931639710394622399451019824572362288458431186299231664459957755422474433520889084351841298056066100216440853409346006657723086501921816381226292526490195810903459483318275931326433052468863850690793659405367902593999395060606972100169925074005992478583035226026829214443008941631771292291305226470216430735050944285543542354459162474346521327649934512511202470099020668235115245819634762067338432916012664452035696422865651002305445711778476072004708256200872226475346448360491248823843688268126341094612981308791499434770936360676087490303951728563482686307164877000300082742316368597958297217061375140696272398140310043942637287763946305961019518639745426370821124559939597559475362769382796386720030343305889701616194279058139516811941262747298761646317383112470923295543635754747288259324745583689440061956478083777663996487389553238481759103908588004219390662578446313004404784835263543083088327198

print(long_to_bytes(decrypt(pubkey, privkey, enc)))
# b'flag{61e19444-7afb-11e9-b704-4ccc6adfc6f0}'