私钥 d 相关攻击

d 泄露攻击

攻击原理

首先当 $d$ 泄露之后，我们自然可以解密所有加密的消息。我们甚至还可以对模数 N 进行分解。其基本原理如下

我们知道 $ed \equiv 1 \bmod \varphi(n)$，那么存在一个 $k$ 使得

$$ed-1=k\varphi(n)$$

又 $\forall a\in {Z}_n^*$，满足$a^{ed-1}\equiv1(\bmod n)$。令

$$ed-1=2^st$$

其中，$t$ 是一个奇数。然后可以证明对于至少一半的 $a\in {Z}_n^*$，存在一个 $i\in[1,s]$，使得

$$a^{2^{i-1}t}\not\equiv\pm1(\bmod n),a^{2^{i}t}\equiv1(\bmod n)$$

成立。如果 $a,i$ 满足上述条件，$gcd(a^{2^{i-1}t}-1,n)$是 $n$ 的一个非平凡因子，所以可以对 $n$ 进行暴力分解。

工具

利用以下工具可以直接进行计算

• RsaConverter.exe (https://sourceforge.net/projects/rsaconverter/ , for windows )
• rsatool.py(分解原理如上)

2017 HITB - hack in the card II

The second smart card sent to us has been added some countermeasures by that evil company. They also changed the public key(attachments -> publickey.pem). However it seems that they missed something......
Can you decrypt the following hex-encoded ciphertext this time?

016d1d26a470fad51d52e5f3e90075ab77df69d2fb39905fe634ded81d10a5fd10c35e1277035a9efabb66e4d52fd2d1eaa845a93a4e0f1c4a4b70a0509342053728e89e977cfb9920d5150393fe9dcbf86bc63914166546d5ae04d83631594703db59a628de3b945f566bdc5f0ca7bdfa819a0a3d7248286154a6cc5199b99708423d0749d4e67801dff2378561dd3b0f10c8269dbef2630819236e9b0b3d3d8910f7f7afbbed29788e965a732efc05aef3194cd1f1cff97381107f2950c935980e8954f91ed2a653c91015abea2447ee2a3488a49cc9181a3b1d44f198ff9f0141badcae6a9ae45c6c75816836fb5f331c7f2eb784129a142f88b4dc22a0a977

这题是接续 2017 HITB - hack in the card I 的一道题，我们直接使用 openssl 查看 publickey.pem 的公钥，发现它的 N 与上一道题的 N 相同，并且上题的 N，e，d 已知。由此可直接使用上面的 rsatool.py 得到 p，q，并通过本题的 e 计算出 e 得到明文。

Wiener's Attack

攻击条件

在 d 比较小（$d<\frac{1}{3}N^{\frac{1}{4}}$）时，攻击者可以使用 Wiener's Attack 来获得私钥。

攻击原理

• https://en.wikipedia.org/wiki/Wiener%27s_attack
• https://sagi.io/2016/04/crypto-classics-wieners-rsa-attack/

工具

• https://github.com/pablocelayes/rsa-wiener-attack
• https://github.com/orisano/owiener

综合例子

2016 HCTF RSA1

这里我们以 2016 年 HCTF 中 RSA 1 - Crypto So Interesting 为例进行分析，源代码链接。

首先先绕过程序的 proof 部分，差不多使用一些随机的数据就可以绕过。

其次，我们来分析一下具体的代码部分，程序是根据我们的 token 来获取 flag 的，这里我们就直接利用源代码中提供的 token。

    print "This is a RSA Decryption System"
    print "Please enter Your team token: "
    token = raw_input()
    try:
        flag = get_flag(token)
        assert len(flag) == 38
    except:
        print "Token error!"
        m_exit(-1)

接下来我们首先知道 $n=pq$，我们再来你仔细分析一下这个 e，d 是如何得到的。

    p=getPrime(2048)
    q=getPrime(2048)
    n = p * q
    e, d = get_ed(p, q)
    print "n: ", hex(n)
    print "e: ", hex(e)

get_ed 函数如下

def get_ed(p, q):
    k = cal_bit(q*p)
    phi_n = (p-1)*(q-1)
    r = random.randint(10, 99)
    while True:
        u = getPrime(k/4 - r)
        if gcd(u, phi_n) != 1:
            continue
        t = invmod(u, phi_n)
        e = pi_b(t)
        if gcd(e, phi_n) == 1:
            break
    d = invmod(e, phi_n)
    return (e, d)

可以看出，我们得到的 u 的位数比 n 的位数的四分之一还要少，这里其实就差不多满足了 Wiener's Attack 了。而且我们计算出来的 u，t，e，d 还满足以下条件

$$\begin{align*} ut &\equiv 1 \bmod \varphi(n) \\ et &\equiv 1 \bmod bt \\ ed &\equiv 1 \bmod \varphi(n) \end{align*}$$

根据题中给出的条件，我们已经知道了 n，e，bt。

所以首先我们可以根据上面的第二个式子知道 e。这时候，可以利用第一个式子进行 Wiener's Attack，获取 u。进而这时我们可以利用私钥指数泄露攻击的方法来分解 N 从而得到 p，q。进而我们就可以得到 d 了。

首先我们绕过 proof 得到了 N，e，加密后的 flag 如下

n:  0x4b4403cd5ac8bdfaa3bbf83decdc97db1fbc7615fd52f67a8acf7588945cd8c3627211ffd3964d979cb1ab3850348a453153710337c6fe3baa15d986c87fca1c97c6d270335b8a7ecae81ae0ebde48aa957e7102ce3e679423f29775eef5935006e8bc4098a52a168e07b75e431a796e3dcd29c98dab6971d3eac5b5b19fb4d2b32f8702ef97d92da547da2e22387f7555531af4327392ef9c82227c5a2479623dde06b525969e9480a39015a3ed57828162ca67e6d41fb7e79e1b25e56f1cff487c1d0e0363dc105512d75c83ad0085b75ede688611d489c1c2ea003c3b2f81722cdb307a3647f2da01fb3ba0918cc1ab88c67e1b6467775fa412de7be0b44f2e19036471b618db1415f6b656701f692c5e841d2f58da7fd2bc33e7c3c55fcb8fd980c9e459a6df44b0ef70b4b1d813a57530446aa054cbfb9d1a86ffb6074b6b7398a83b5f0543b910dcb9f111096b07a98830a3ce6da47cd36b7c1ac1b2104ea60dc198c34f1c50faa5b697f2f195afe8af5d455e8ac7ca6eda669a5a1e3bfbd290a4480376abd1ff21298d529b26a4e614ab24c776a10f5f5d8e8809467a3e81f04cf5d5b23eb4a3412886797cab4b3c5724c077354b2d11d19ae4e301cd2ca743e56456d2a785b650c7e1a727b1bd881ee85c8d109792393cc1a92a66b0bc23b164146548f4e184b10c80ec458b776df10405b65399e32d657bc83e1451
e:  0x10194521505692a64d043daaef7647e0efb1503ec89220a0e4148ab53ecf708146a8893a2e700e4f2f062be14a3ab4e46339a939d5c7289904cc0ab043320d3a4d7da868bf5736ae5f787d6c0e3d9b8cc4b81314ad6c5ff643bc0d8946fea7eb09bf707a54747a39df1cfc0c30849770578cb63de86621001ce86a11874c91419a4d07373e66e94f31b988cac3aeaff88c7abaf3b78468a434990f7854e734208a7461f8245660fa8301f979e85517d705302c797dbdf2938cc442b01c228939eb73aa29651a198a332af2bb982310699684e5a0595c7413ec01eefb3613a9ea4b59f1de984ad4bf6654960613c0f8104b4e41fb33384e07f715176d68f4bb7613b1258675e70dc774f701aee053830f0be28ba9f308c9fe1707a5ba07a2027d74144b8aeb4042df3c1d73d9c38c2d7d1a890fd70d6e38c72da5d075f3811c0354dcecdd836a59112a70be22757278c5e4973906aaeeadd6f61d0845d6f9761df191b0b2527d122dd07f8bd07f5cd14268246ac2b93b778c84b5157f7eb23a8eaa9f0f885f2a38e3fb8fd1012d9b6c841cea8d9d73b232bef298afd086c1063bdd11e0777c8d2ec91ae843a67a98039cb53fad0ee25040176841a017fabf79b98de21d40bc6985f82dd84406aad26e9ac9bc5f6e12385230d9620b888c201ca9c413cbf0f36b100a6c62c5c8f065934fcf9f9f0179eea35888cb357b704441c1
flag:  0x2517d1866acc5b7b802a51d6251673262e9e6b2d0e0e14a87b838c2751dee91e4ea29019b0a7877b849fddf9e08580d810622db538462b529412eba9d0f8a450fe1889021c0bbd12a62ccc3fff4627b1dbdebec3a356a066adc03f7650722a34fe41ea0a247cb480a12286fffc799d66b6631a220b8401f5f50daa12943856b35e59abf8457b2269efea14f1535fb95e56398fd5f3ac153e3ea1afd7b0bb5f02832883da46343404eb44594d04bbd254a9a35749af84eaf4e35ba1c5571d41cab4d58befa79b6745d8ecf93b64dd26056a6d1e82430afbff3dbc08d6c974364b57b30c8a8230c99f0ec3168ac4813c4205d9190481282ae14f7b94400caff3786ed35863b66fefcffbef1ad1652221746a5c8da083987b2b69689cf43e86a05ce4cf059934716c455a6410560e41149fbcf5fcea3c210120f106b8f6269b9a954139350626cf4dcb497ce86264e05565ec6c6581bf28c643bb4fab8677148c8034833cedacb32172b0ff21f363ca07de0fa2882ac896954251277adc0cdd0c3bd5a3f107dbebf5f4d884e43fe9b118bdd51dc80607608670507388ae129a71e0005826c7c82efccf9c86c96777d7d3b9b5cce425e3dcf9aec0643f003c851353e36809b9202ff3b79e8f33d40967c1d36f5d585ac9eba73611152fc6d3cf36fd9a60b4c621858ed1f6d4db86054c27828e22357fa3d7c71559d175ff8e8987df

其次使用如下方法进行 Wiener's Attack 得到 u，如下

if __name__ == "__main__":
    bt = 536380958350616057242691418634880594502192106332317228051967064327642091297687630174183636288378234177476435270519631690543765125295554448698898712393467267006465045949611180821007306678935181142803069337672948471202242891010188677287454504933695082327796243976863378333980923047411230913909715527759877351702062345876337256220760223926254773346698839492268265110546383782370744599490250832085044856878026833181982756791595730336514399767134613980006467147592898197961789187070786602534602178082726728869941829230655559180178594489856595304902790182697751195581218334712892008282605180395912026326384913562290014629187579128041030500771670510157597682826798117937852656884106597180126028398398087318119586692935386069677459788971114075941533740462978961436933215446347246886948166247617422293043364968298176007659058279518552847235689217185712791081965260495815179909242072310545078116020998113413517429654328367707069941427368374644442366092232916196726067387582032505389946398237261580350780769275427857010543262176468343294217258086275244086292475394366278211528621216522312552812343261375050388129743012932727654986046774759567950981007877856194574274373776538888953502272879816420369255752871177234736347325263320696917012616273L
    e = 0x10194521505692a64d043daaef7647e0efb1503ec89220a0e4148ab53ecf708146a8893a2e700e4f2f062be14a3ab4e46339a939d5c7289904cc0ab043320d3a4d7da868bf5736ae5f787d6c0e3d9b8cc4b81314ad6c5ff643bc0d8946fea7eb09bf707a54747a39df1cfc0c30849770578cb63de86621001ce86a11874c91419a4d07373e66e94f31b988cac3aeaff88c7abaf3b78468a434990f7854e734208a7461f8245660fa8301f979e85517d705302c797dbdf2938cc442b01c228939eb73aa29651a198a332af2bb982310699684e5a0595c7413ec01eefb3613a9ea4b59f1de984ad4bf6654960613c0f8104b4e41fb33384e07f715176d68f4bb7613b1258675e70dc774f701aee053830f0be28ba9f308c9fe1707a5ba07a2027d74144b8aeb4042df3c1d73d9c38c2d7d1a890fd70d6e38c72da5d075f3811c0354dcecdd836a59112a70be22757278c5e4973906aaeeadd6f61d0845d6f9761df191b0b2527d122dd07f8bd07f5cd14268246ac2b93b778c84b5157f7eb23a8eaa9f0f885f2a38e3fb8fd1012d9b6c841cea8d9d73b232bef298afd086c1063bdd11e0777c8d2ec91ae843a67a98039cb53fad0ee25040176841a017fabf79b98de21d40bc6985f82dd84406aad26e9ac9bc5f6e12385230d9620b888c201ca9c413cbf0f36b100a6c62c5c8f065934fcf9f9f0179eea35888cb357b704441c1
    t = gmpy2.invert(e, bt)
    n = 0x4b4403cd5ac8bdfaa3bbf83decdc97db1fbc7615fd52f67a8acf7588945cd8c3627211ffd3964d979cb1ab3850348a453153710337c6fe3baa15d986c87fca1c97c6d270335b8a7ecae81ae0ebde48aa957e7102ce3e679423f29775eef5935006e8bc4098a52a168e07b75e431a796e3dcd29c98dab6971d3eac5b5b19fb4d2b32f8702ef97d92da547da2e22387f7555531af4327392ef9c82227c5a2479623dde06b525969e9480a39015a3ed57828162ca67e6d41fb7e79e1b25e56f1cff487c1d0e0363dc105512d75c83ad0085b75ede688611d489c1c2ea003c3b2f81722cdb307a3647f2da01fb3ba0918cc1ab88c67e1b6467775fa412de7be0b44f2e19036471b618db1415f6b656701f692c5e841d2f58da7fd2bc33e7c3c55fcb8fd980c9e459a6df44b0ef70b4b1d813a57530446aa054cbfb9d1a86ffb6074b6b7398a83b5f0543b910dcb9f111096b07a98830a3ce6da47cd36b7c1ac1b2104ea60dc198c34f1c50faa5b697f2f195afe8af5d455e8ac7ca6eda669a5a1e3bfbd290a4480376abd1ff21298d529b26a4e614ab24c776a10f5f5d8e8809467a3e81f04cf5d5b23eb4a3412886797cab4b3c5724c077354b2d11d19ae4e301cd2ca743e56456d2a785b650c7e1a727b1bd881ee85c8d109792393cc1a92a66b0bc23b164146548f4e184b10c80ec458b776df10405b65399e32d657bc83e1451
    solve(n, t)

其中 solve 函数就是对应的 Wiener's Attack 的函数。

我们得到了 u，如下

➜  rsa-wiener-attack git:(master) ✗ python RSAwienerHacker.py
Testing Wiener Attack
Hacked!
('hacked_d = ', mpz(404713159471231711408151571380906751680333129144247165378555186876078301457022630947986647887431519481527070603810696638453560506186951324208972060991323925955752760273325044674073649258563488270334557390141102174681693044992933206572452629140703447755138963985034199697200260653L))
-------------------------
Hacked!
('hacked_d = ', mpz(404713159471231711408151571380906751680333129144247165378555186876078301457022630947986647887431519481527070603810696638453560506186951324208972060991323925955752760273325044674073649258563488270334557390141102174681693044992933206572452629140703447755138963985034199697200260653L))
-------------------------
Hacked!
('hacked_d = ', mpz(404713159471231711408151571380906751680333129144247165378555186876078301457022630947986647887431519481527070603810696638453560506186951324208972060991323925955752760273325044674073649258563488270334557390141102174681693044992933206572452629140703447755138963985034199697200260653L))
-------------------------
Hacked!
('hacked_d = ', mpz(404713159471231711408151571380906751680333129144247165378555186876078301457022630947986647887431519481527070603810696638453560506186951324208972060991323925955752760273325044674073649258563488270334557390141102174681693044992933206572452629140703447755138963985034199697200260653L))
-------------------------
Hacked!
('hacked_d = ', mpz(404713159471231711408151571380906751680333129144247165378555186876078301457022630947986647887431519481527070603810696638453560506186951324208972060991323925955752760273325044674073649258563488270334557390141102174681693044992933206572452629140703447755138963985034199697200260653L))

接着利用 RsaConverter 以及 u，t，n 获取对应的 p 和 q。如下

94121F49C0E7A37A60FDE4D13F021675ED91032EB16CB070975A3EECECE8697ED161A27D86BCBC4F45AA6CDC128EB878802E0AD3B95B2961138C8CD04D28471B558CD816279BDCCF8FA1513A444AF364D8FDA8176A4E459B1B939EBEC6BB164F06CDDE9C203C612541E79E8B6C266436AB903209F5C63C8F0DA192F129F0272090CBE1A37E2615EF7DFBB05D8D88B9C964D5A42A7E0D6D0FF344303C4364C894AB7D912065ABC30815A3B8E0232D1B3D7F6B80ED7FE4B71C3477E4D6C2C78D733CF23C694C535DB172D2968483E63CC031DFC5B27792E2235C625EC0CFDE33FD3E53915357772975D264D24A7F31308D72E1BD7656B1C16F58372E7682660381
8220863F1CFDA6EDE52C56B4036485DB53F57A4629F5727EDC4C5637603FE059EB44751FC49EC846C0B8B50966678DFFB1CFEB350EC44B57586A81D35E4887F1722367CE99116092463079A63E3F29D4F4BC416E7728B26248EE8CD2EFEA6925EC6F455DF966CEE13C808BC15CA2A6AAC7FEA69DB7C9EB9786B50EBD437D38B73D44F3687AEB5DF03B6F425CF3171B098AAC6708D534F4D3A9B3D43BAF70316812EF95FC7EBB7E224A7016D7692B52CB0958951BAB4FB5CB1ABB4DAC606F03FA15697CC3E9DF26DE5F6D6EC45A683CD5AAFD58D416969695067795A2CF7899F61669BC7543151AB700A593BF5A1E5C2AFBCE45A08A2A9CC1685FAF1F96B138D1

然后我们直接去获得 d，进而就可以恢复明文

    p = 0x94121F49C0E7A37A60FDE4D13F021675ED91032EB16CB070975A3EECECE8697ED161A27D86BCBC4F45AA6CDC128EB878802E0AD3B95B2961138C8CD04D28471B558CD816279BDCCF8FA1513A444AF364D8FDA8176A4E459B1B939EBEC6BB164F06CDDE9C203C612541E79E8B6C266436AB903209F5C63C8F0DA192F129F0272090CBE1A37E2615EF7DFBB05D8D88B9C964D5A42A7E0D6D0FF344303C4364C894AB7D912065ABC30815A3B8E0232D1B3D7F6B80ED7FE4B71C3477E4D6C2C78D733CF23C694C535DB172D2968483E63CC031DFC5B27792E2235C625EC0CFDE33FD3E53915357772975D264D24A7F31308D72E1BD7656B1C16F58372E7682660381
    q = 0x8220863F1CFDA6EDE52C56B4036485DB53F57A4629F5727EDC4C5637603FE059EB44751FC49EC846C0B8B50966678DFFB1CFEB350EC44B57586A81D35E4887F1722367CE99116092463079A63E3F29D4F4BC416E7728B26248EE8CD2EFEA6925EC6F455DF966CEE13C808BC15CA2A6AAC7FEA69DB7C9EB9786B50EBD437D38B73D44F3687AEB5DF03B6F425CF3171B098AAC6708D534F4D3A9B3D43BAF70316812EF95FC7EBB7E224A7016D7692B52CB0958951BAB4FB5CB1ABB4DAC606F03FA15697CC3E9DF26DE5F6D6EC45A683CD5AAFD58D416969695067795A2CF7899F61669BC7543151AB700A593BF5A1E5C2AFBCE45A08A2A9CC1685FAF1F96B138D1
    if p * q == n:
        print 'true'
    phin = (p - 1) * (q - 1)
    d = gmpy2.invert(e, phin)
    cipher = 0x2517d1866acc5b7b802a51d6251673262e9e6b2d0e0e14a87b838c2751dee91e4ea29019b0a7877b849fddf9e08580d810622db538462b529412eba9d0f8a450fe1889021c0bbd12a62ccc3fff4627b1dbdebec3a356a066adc03f7650722a34fe41ea0a247cb480a12286fffc799d66b6631a220b8401f5f50daa12943856b35e59abf8457b2269efea14f1535fb95e56398fd5f3ac153e3ea1afd7b0bb5f02832883da46343404eb44594d04bbd254a9a35749af84eaf4e35ba1c5571d41cab4d58befa79b6745d8ecf93b64dd26056a6d1e82430afbff3dbc08d6c974364b57b30c8a8230c99f0ec3168ac4813c4205d9190481282ae14f7b94400caff3786ed35863b66fefcffbef1ad1652221746a5c8da083987b2b69689cf43e86a05ce4cf059934716c455a6410560e41149fbcf5fcea3c210120f106b8f6269b9a954139350626cf4dcb497ce86264e05565ec6c6581bf28c643bb4fab8677148c8034833cedacb32172b0ff21f363ca07de0fa2882ac896954251277adc0cdd0c3bd5a3f107dbebf5f4d884e43fe9b118bdd51dc80607608670507388ae129a71e0005826c7c82efccf9c86c96777d7d3b9b5cce425e3dcf9aec0643f003c851353e36809b9202ff3b79e8f33d40967c1d36f5d585ac9eba73611152fc6d3cf36fd9a60b4c621858ed1f6d4db86054c27828e22357fa3d7c71559d175ff8e8987df
    flag = gmpy2.powmod(cipher, d, n)
    print long_to_bytes(flag)

得到 flag

true
hctf{d8e8fca2dc0f896fd7cb4cb0031ba249}

参考文献

• http://cacr.uwaterloo.ca/hac/about/chap8.pdf