查看: 125|回复: 0

[Reverse] 算法逆向6—RSA识别

[复制链接]
发表于 2020-6-4 00:36:31 | 显示全部楼层 |阅读模式
  本文原创作者:i春秋作家——icq5f7a075d
  1. 算法介绍
  RSA算法是一种用数论构造的、基于大合数因子分解困难性的公开密钥密码。由于RSA密码既可用于加密,又可用于数字签名,安全、易懂,因此RSA密码已成为目前应用最广泛的公开密钥密码。许多勒索软件就是使用RSA加密,在没有私钥的情况下很难恢复数据。
  在正式介绍RSA加密算法前,我们还需要知道一些数论的概念:
  (1)互素关系(互质关系):如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互素关系(互质关系);
  (2)乘法逆元(模反元素):如果两个正整数a和n互质,那么一定可以找到整数b,使得ab-1被n整除,或者说ab被n除的余数是1。这时,b就叫做a的乘法逆元(模反元素)。
  (3)欧拉函数;任意给定正整数n,计算小于n的正整数中与n互质的数的数目的方式就叫做欧拉函数,以φ(n)表示。如果n是质数,则 φ(n)=n-1 ,因为质数与小于它的每一个数,都构成互质关系。如果n可以分解成两个互质的整数之积,n = p1 × p2,则φ(n) =φ(p1p2) = φ(p1)φ(p2)=(p1-1)*(p2-1)。
  (4)欧拉定理:如果两个正整数a和n互质,则n的欧拉函数φ(n)可以让下面的等式成立:
  a^φ(n)=1 (mod n)
  有了以上数论的知识,我们就可以理解RSA加密算法了。
  加密算法描述
  (1)密钥的产生
  a.选两个保密的大素数(素数又称质数)p和q;
  b.计算n=p*q,φ(n) =(p-1)(q-1);
  c.选一整数e,满足1<e<φ(n),且φ(n)与e互质;
  d.计算d,满足d*e=1 (mod φ(n)),即d是e在φ(n)下的乘法逆元,因e与φ(n)互素,由模运算可知,它的乘法逆元一定存在;
  e.以{e,n}为公开钥,{d,n}为秘密钥;
  (2)加密
  加密时首先将明文比特串分组,使得每个分组对应的十进制数小于n,即分组长度小于log 2 n,然后对每个明文分组m,作加密运算:c=m^e mod n ;
  (3)解密
  对密文分组的解密运算为:m=c^d mod n ;
  2. RSA24程序逆向
  24指的是密钥长度。
  2.1. 定位关键位置

算法逆向6—RSA识别

算法逆向6—RSA识别

算法逆向6—RSA识别

算法逆向6—RSA识别

算法逆向6—RSA识别

算法逆向6—RSA识别
  数据验证的过程在sub_4029B0中进行,也是RSA计算的过程。
  2.2. Serial计算
  小知识点:计算字符串长度:
cld  xor eax,eax
  or ecx,-0x1     ;ecx=0xFFFFFFFF
  repne  scas  byte ptr es:[edi] ; [edi]=字符串
  not ecx
  dec ecx    ;计算出字符串长度

算法逆向6—RSA识别

算法逆向6—RSA识别

算法逆向6—RSA识别

算法逆向6—RSA识别

算法逆向6—RSA识别

算法逆向6—RSA识别

算法逆向6—RSA识别

算法逆向6—RSA识别
  计算的过程可以用如下代码表示:
  一个经典的 m e  mod n 算法:
m=7167622 #m的值不固定  n=12790891L
  e=9901
  c=1
  while(e>0):
  if(e%2==0):
  e=e>>1
  m=(m*m)%n
  else:
  e=e-1
  c=(c*m)%n
  print c

算法逆向6—RSA识别

算法逆向6—RSA识别
  3. 总结
  RSA的学习需要较高的理论基础,但是RSA实际上很简单,反汇编出的程序流程简单,很容易识别。
  文末照例来点彩蛋:
  ① 在线分解质因数[/url] :http://www.atool.org/quality_factor.php
  ②python中 的 gmpy2 模块。
  gmpy2是Python的一个扩展库, 可以进行高精度运算,适用于 Miller-Rabin素数测试算法、大素数生成、欧几里德算法、求域中元素的逆、Jacobi符号、legendre符号等 。
  RSA中经常进行 大素数 计算,gmpy2模块是一个不错的选择。
  本次逆向程序中的n=12790891,e=9901,使用 在线分解质因数[/url] 工具,很容易计算出q=1667,p=7673,分解出借助 gmpy2 模块计算d,d= gmpy2.invert(e, (p-1)*(q-1)) 。 q,p,n,d,e都有了,我们可以进行任意的RSA加密解密了。
  注册机:
import gmpy2  n=12790891L
  e=9901
  c1=8483678
  c2=5666933
  q=1667
  p=7673
  d=gmpy2.invert(e, (p-1)*(q-1))
  m1=pow(c1,d,n)
  m2=pow(c2,d,n)
  print m1,m2

  本文属i春秋原创奖励计划,未经许可禁止转载!
  本文如果出现错误,欢迎指出,感激不尽!
  本文中的所有程序请在虚拟机中运行。
  参考资料:
  《加密与解密实战攻略》
  《应用密码学》 曹天杰著



温馨提示:
1.如果您喜欢这篇帖子,请给作者点赞评分,点赞会增加帖子的热度,评分会给作者加学币。(评分不会扣掉您的积分,系统每天都会重置您的评分额度)。
2.回复帖子不仅是对作者的最好奖励,还可以获得学币奖励,请尊重作者的劳动成果,拒绝做伸手党!
3.发广告、灌水回复等违规行为一经发现直接禁言,如果本帖内容涉嫌违规,请点击论坛底部的举报反馈按钮,也可以在【投诉建议】板块发帖举报。
论坛交流群:672619046
微信公众号
快速回复 返回顶部 返回列表