RSA 算法的加密方法(对大数的)解析 之二

tfrist

接上篇 RSA 算法的加密方法(对大数的)解析 之一，这里 https://www.52pojie.cn/thread-1324005-1-1.html.

感谢大家捧场观看。 有了上一篇的理论，这一篇我主要展示一个应用中，它是如何加密大数的。如果您还没有看过上一篇帖子，我强烈建议先去看看上一篇的内容，这样对理解本篇是事半功倍的功效。闲话少说了，here we go.





4 实际案例解析

以下是一个实例。 要加密的数据是80H长的大数. e是16.  N也是80H长的大数. 最终加密后的数据（大余数）是80H长的大数.




上面所示的是运行完成的结果。 接下来我会用实例来看看它的过程是什么样的，那同时也是在软件中怎样实现大数的相乘，相除，取余运算的。
首先让我们看一些两个大数的平方是如何做的。因为大数不是整数，长整数等，几条指令就可以搞定的相乘，相除，取余。他不仅需要开辟特别的内存空间来存储原大数，结果大数等而且一般在软件中都需要一个专门的方法来实现。下面插图中就是我分析的一个软件中在调用一个方法来执行大数的乘法运算（两个相同的相乘就是平方，要是拿结果再乘一个相同的大数就是乘方依次类推）。




在上图的代码中，这个方法的第二个参数和第三个参数都是乘数对象，每个乘数对象里面包含着一个大数. 这里可以看到都是相同的edi. 那么当下这个方法要执行的就是edi里面那个大数的平方. 即edi*edi.   运算的结果存在另一个大数对象中并返回这个对象在eax中。



上图是执行大数平方的过程，右侧是结果，可以观察到结果大数的数据量是原大数的一倍。也就是计算上一篇中提到C代码Ori_data = (Ori_data * Ori_data) % N;目前平方部分(Ori_data * Ori_data)已经计算完成. 接下来就是用平方的结果大数去除N来取余.
以下是调用大数除法的方法。注意到了吗，除法方法就在大数乘法的下面，eax是平方结果的大数对象，现在作为被除数压入大数除法方法的第二个参数，其第三个参数就是除数N.  这个相除方法会产生一个商和一个余数，这里商对我们来说无用，所以丢弃，余数也是一个大数保存在一个大数对象中并返回在eax寄存器中。


一次的运算结果如下图所示:

以上图中所示就是在执行C代码中Ori_data = (Ori_data * Ori_data) % N;的后半部分即取余过程  (平方的值)%N.


以下将对大数间相乘的过程进行简要描述，以及最后我会对大数相乘的代码进行展示：
任何大数的相乘运算（相除也是）都要把他们降到小数级别像int 或者short层次来实现。仔细看任何大数都是有一个个的short数 (2字节的word)或者int （4字节的int）来组成的。大数相乘的方法的工作就是从大数中一个个的遍历出这些小数，然后执行这些小数的相乘运算。
大致就是这样的过程:先读取第一个short数从一个大数中,然后用它去一个个的乘从另一个大数中读取的所有short，每次的结果都依次的存入结果大数内存中。乘的过程中必然会有进位的情况，进位要保存并且同下一次相乘的结果相加实现进位。(大道至简，仔细想想这个操作就跟我们计算2个数相加一样，有进位的时候是不是进位上去然后等着那一位上的数相加结果在加进位的数？)，当第一个short数同另一个大数中的所有short数乘晚一边后，再从第一个大数中读取第二个short数，然后用它同第二个大数中的所有short数相乘并结果记录到结果大数内存中，依照以上的顺序当把第一个大数的最后一个short同另一个大数运算完了之后，在结果大数中存储的就是运算结果。这就完成了两个大数的相乘操作。

以下是部分截取的相乘方法中的ASM代码，实现依次取short数然后同另一个大数的所有short数相乘的循环。外层循环是依次取第一个数的short数，内层循环是依次取另一个大数的所有short数同第一个大数的short数相乘。众客观请上眼:
[...]
|------>     00407F51 loc_407F51:   ; 外层循环第一个大数中的short            
|                00407F51        mov     ecx, [ebp+var_4]
|                00407F54        xor     edx, edx
|                00407F56        mov     [ebp+var_C], edx
|                00407F59
|          -> 00407F59 loc_407F59: ; 内层循环，用外层的short同另一个大数的所有short乘一遍。
|        |        00407F59        movzx   eax, word ptr [ebx+edx*2] ;循环获取所有short数。
|        |        00407F5D        mov     edi, [ebp+var_8]  
|        |        00407F60        movzx   edi, word ptr [edi]  ;;; 取外层short数
|        |        00407F63        imul    eax, edi  ;;两个short数相乘
|        |        00407F66        movzx   edi, word ptr [esi+ecx*2]
|        |        00407F6A        add     eax, edi  ;外层上一轮运算中进位
|        |        00407F6C        movzx   edi, word ptr [ebp+var_C]
|        |        00407F70        add     eax, edi   ;;上次进位累加
|        |        00407F72        mov     [esi+ecx*2], ax ;;结果存入结果大数中
|        |        00407F76        shr     eax, 10h
|        |        00407F79        inc     ecx  ;;; 结果大数指针累加
|        |        00407F7A        inc     edx  ;; 另一个大数的指针，累加指向下一个short数
|        |        00407F7B        mov     [ebp+var_C], eax ;;存储进位，作为下次进位
|        |        00407F7E        cmp     edx, [ebp+var_10]
|        - ---  00407F81        jl      short loc_407F59
|                00407F83        inc     [ebp+var_4]
|                00407F86        add     [ebp+var_8], 2  ;;; 指向第一个大数的下一个short数
|                00407F8A        mov     [esi+ecx*2], ax ;;记录当前进位标志到结果大数中.
|                00407F8E        mov     eax, [ebp+var_4]
|                00407F91        cmp     eax, [ebp+var_14]
----------  00407F94        jl      short loc_407F51
                00407F96        mov     ecx, [ebp+arg_4]
                00407F99        mov     eax, [ebp+arg_0]
                00407F9C        call    sub_407951
                00407FA1        mov     ecx, [ebp+arg_8]
[...]

除法和取余的方法我就不在这里展示了，可以自己去想想无非就是乘法方法的逆操作，也是把大数变成小数来做除法，在被除数里面取int数去除以从除数中取的short数，依次的内外层循环计算，想想我们平时的除法过程是什么样的，就大概明白了吧。



好了就到这里的，如果您从本文中学到了一点东西，我深感欣慰，因为我的努力没有白费。那么在下次的分析中再遇到这样的代码结构，你能识别出来这是经过优化后的RSA算法吗？ 如果能那就太好了。
I hope you are able to get this skill through my analysis!!! Good Luck, everybody.

------------------------------------------- The End ---------------------------------------

tfrist

yzyuan007 发表于 2020-12-10 08:44
2017年中了RSA4096病毒，几乎所有文件都被瞬间加密，勒索比特币赎金，忍痛全部删除。

很多勒索软件都或多或少的会用到RSA算法。 RSA+RC4  RSA+AES等。

liaochitech

yzyuan007 发表于 2020-12-10 08:44
2017年中了RSA4096病毒，几乎所有文件都被瞬间加密，勒索比特币赎金，忍痛全部删除。

所以备份文件还是有必要的

zipl1985

高深，学习了

lyliucn

继续学习！！！

Yusica

谢谢，学到了，学到了

zudeng

谢谢楼主分享，谢谢

ifenglmy

谢谢楼主分享。。

shencaineng

学习到了谢谢大佬

咋也学不会

刚遇到一个RC4+RSA 的样本就看见大神讲课了
学习了

啊物理

好厉害，谢谢楼主