RSA之共模攻击 | Venture's Blog

共模攻击

最近巅峰极客线上第二场遇到了RSA的共模攻击，本身不难，但是还是踩了一些坑。。。记录一下

可攻击的原因在于两个用户使用了相同的模数N，不同的私钥，并加密同一明文消息

由以上的条件，设明文消息为m,两个用户选择的公钥分别为$ e_i $和$ e_j $,且$ e_i$和$ e_j $互素，对于同一明文m加密有：
$$
c_i=m^ei(mod\quad N),c_j=m^{e_j}(mod\quad N)
$$
又因$ e_i $和$ e_j $互素,必存在整数s和t,满足$se_i+te_j=1$, 从而$c_i^sc_j^t=m^{se_i+te_j}=m(mod\quad N)$

题目直接给到的是两个密文文件，两个公钥文件，这里需要使用openssl查看具体的公钥参数

openssl rsa -pubin -in pubkey1.pem -text -modulus

提取出N和e

分别提取pubkey1.pem和pubkey2.pem，可以看到N相同，e1=2333,e2=23333

满足共模攻击条件

而这里还需要把密文从base64转换成16进制数,可以使用

echo base64编码密文 |openssl base -d |xxd -ps

贴出一个jio本

# -*- coding: utf-8 -*-
from libnum import n2s,s2n
from gmpy2 import invert
# 递归实现欧几里得算法
def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)
def main():
  n = 0x8989A398988456B3FEF4A6AD86DF3C99577F8978048DE5436BEFC30D8D8C94958912AA526FF333B66857306EBB8DE36C2C396A84EFDC5D382502DAA1A3F3B6E97502D2E31C849330F5B4C95257A149A97F5954EAF89341147ADCDD4E950FFF74E30BBE622876B42EEAC86DF4AD9715D05B5604AA8179424C7D9AC46BD6B5F322B2B5728BA148704A25A8EFCC1E7C84EA7E5CE3E01703F04F94A431D9954BD7AE2C7DD6E879B35F8A2D4A5EFBE737257BF99BD9EE66B15AFF233FC77B558A487DA5952FBE2B923DA9C5EB46788C050336B7E36A5ED82D5C1B2AEB0E45BEE405CBE72481DB2568AA829EEAC87D201A5A8FF5EE6F0BE38192AB2839635F6C664217
  c1 = 0x5d22812766e24ba6eb0b9886c14d06662b477553371d7022c2d16755fdbe1d3694a856a1c4bf81c418b6403731ee02f172311608cc053fa0d2f769cc014e2bd203d6484508a18e7bb20359b230c80c0ba489878b343520633fb53fe9c5e1f93b8303dda33ac8bc05c60c1bcc063baf8aab02f2f9953f723a78b2e4b7d0b8e8716dd12070e7271f0235680c5dabeffe01d540ece06d1da480d40a4e2485ecf382ab299fab6ab70386076eefaca7a0a0bfc59709aeb45608b9128a0812b1df273fa9f59767ce0ea3c9cfaa06b180397159e2ed18cf59a2ec052a76a09a36e71fee7c3deb1cc385d869f5caa858d0cf75eb2bfb9411213c8c81083de2f5fbcc94a7
  c2 = 0x12bbb3c150174952c2deb95d8dcb31e873b4514202751f71c60afd796361216d13f25d8edf24ff2e514b2b6f985341c1f7bc6be476a265eb24e13e88b89f7e88ecc1f184a458c7d8bce4832a7ec99e0ff5437c10ba895d9be52eae6664884b3d9058be121b023406d50272f32d72f0cd89b77a66a6b9e0eaaeee03a28fe548ccfca74fa3ab3db81ec70937db2153ce565f8267816f764441c757cacf1da8ac09dc5e02cfae3f24cdccee086f00da26fc37651fcba389b52b6430f0f6d89ce72056bf42591ee6572c687e85a4eaa5a941fdddd1f5fac1b6cf710917c679ea2d6cb94b73d970d41ad7091f4532493b4dd098d56c3a2bd719bdc6ce67996f199585
  e1 = 2333
  e2 = 23333
  s = egcd(e1, e2)
  s1 = s[1]
  s2 = s[2]
# 求模反元素
  if s1<0:
    s1 = - s1
    c1 = invert(c1, n)
  elif s2<0:
    s2 = - s2
    c2 = invert(c2, n)
  m = pow(c1,s1,n)*pow(c2,s2,n) % n
  print n2s(m)
if __name__ == '__main__':
  main()

求模反元素那里，是因为若$s_1$<0,则$c_1^{s_1}==(c_1^{-1})^{-s_1}$

另一些常用的openssl命令

解密：

openssl rsautl -decrypt -inkey private.pem -in flag.enc -out flag

openssl rsautl -decrypt -in flag.enc -inkey private.key -out flag.de

openssl rsautl -decrypt -in flag.enc -inkey private.key -out flag.de -oaep

openssl rsautl -decrypt -in flag.enc-inkey private.key -out flag.de -pkcs

私钥签名:

openssl rsautl -sign -in test -out test.sig-inkey asn1enc.pem

公钥验证:

openssl rsautl -verify -in test.sig -out test.vfy -inkey asn1pub.pem -pubin

参考：

https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_module_attack/#_6

https://www.cnblogs.com/gwind/p/8013154.html

https://blog.csdn.net/like98k/article/details/79352076