📄 helpdlg.cpp
字号:
#include "stdafx.h"
#include "RsaKit.h"
#include "HelpDlg.h"
CHelpDlg::CHelpDlg(CWnd* pParent /*=NULL*/)
: CDialog(CHelpDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CHelpDlg)
//}}AFX_DATA_INIT
}
void CHelpDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CHelpDlg)
DDX_Control(pDX, IDC_EDIT, m_Edit);
DDX_Control(pDX, IDC_TREE, m_Tree);
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CHelpDlg, CDialog)
//{{AFX_MSG_MAP(CHelpDlg)
ON_NOTIFY(TVN_SELCHANGED, IDC_TREE, OnSelchangedTree)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
BOOL CHelpDlg::OnInitDialog()
{
CDialog::OnInitDialog();
TV_INSERTSTRUCT TreeCtrlItem;
TreeCtrlItem.hParent = TVI_ROOT;
TreeCtrlItem.hInsertAfter = TVI_LAST;
TreeCtrlItem.item.mask = TVIF_TEXT | TVIF_PARAM;
TreeCtrlItem.item.pszText = _T("前言");
TreeCtrlItem.item.lParam = 0;
HTREEITEM hTreeItem0 = m_Tree.InsertItem(&TreeCtrlItem);
TreeCtrlItem.hParent = TVI_ROOT;
TreeCtrlItem.hInsertAfter = TVI_LAST;
TreeCtrlItem.item.mask = TVIF_TEXT | TVIF_PARAM;
TreeCtrlItem.item.pszText = _T("原理介绍");
TreeCtrlItem.item.lParam = 1;
HTREEITEM hTreeItem1 = m_Tree.InsertItem(&TreeCtrlItem);
TreeCtrlItem.hParent = hTreeItem1;
TreeCtrlItem.item.pszText = _T("大数存储");
TreeCtrlItem.item.lParam = 2;
m_Tree.InsertItem(&TreeCtrlItem);
TreeCtrlItem.hParent = hTreeItem1;
TreeCtrlItem.item.pszText = _T("加减乘除");
TreeCtrlItem.item.lParam = 3;
m_Tree.InsertItem(&TreeCtrlItem);
TreeCtrlItem.hParent = hTreeItem1;
TreeCtrlItem.item.pszText = _T("欧几里德方程");
TreeCtrlItem.item.lParam = 4;
m_Tree.InsertItem(&TreeCtrlItem);
TreeCtrlItem.hParent = hTreeItem1;
TreeCtrlItem.item.pszText = _T("模幂运算");
TreeCtrlItem.item.lParam = 5;
m_Tree.InsertItem(&TreeCtrlItem);
TreeCtrlItem.hParent = hTreeItem1;
TreeCtrlItem.item.pszText = _T("模乘运算");
TreeCtrlItem.item.lParam = 6;
m_Tree.InsertItem(&TreeCtrlItem);
TreeCtrlItem.hParent = hTreeItem1;
TreeCtrlItem.item.pszText = _T("蒙哥马利模乘");
TreeCtrlItem.item.lParam = 7;
m_Tree.InsertItem(&TreeCtrlItem);
TreeCtrlItem.hParent = hTreeItem1;
TreeCtrlItem.item.pszText = _T("素数测试");
TreeCtrlItem.item.lParam = 8;
m_Tree.InsertItem(&TreeCtrlItem);
m_Tree.Expand(hTreeItem1,TVE_EXPAND);
m_Edit.SetMargins(5,5);
return TRUE;
}
void CHelpDlg::OnSelchangedTree(NMHDR* pNMHDR, LRESULT* pResult)
{
NM_TREEVIEW* pNMTreeView = (NM_TREEVIEW*)pNMHDR;
switch(pNMTreeView->itemNew.lParam)
{
case 0:
m_Text="";
m_Text+="\r\n";
m_Text+=" 俺曾经查阅了网上找得到的各种用于实现RSA 的大数运算库，然而最终还是决\r\n";
m_Text+="定自己动手写一个。因为凡是效率高速度快的代码（crypto++、miracl、freelip、\r\n";
m_Text+="rsaref等），要么使用的数据结构过于复杂，要么编码风格杂乱无章，俺的水平和\r\n";
m_Text+="耐心都实在是有限，以至于无法读懂这些东西。而俺读得懂的一些代码，其实现方\r\n";
m_Text+="式却又过于幼稚，效率极低速度一塌糊涂。俺觉得像俺这样的人不在少数，于是决\r\n";
m_Text+="心写一个清晰易懂，效率也过得去的东西奉献给大家。\r\n\r\n";
m_Text+=" 这个函数库刚做好的时候，生成1024位的随机密钥耗时大约5 分钟，俺认为是\r\n";
m_Text+="可以接受的。但后来找到一个叫tE! 的老外用miracl库写的RsaTools，发现其生成\r\n";
m_Text+="1024位的密钥耗时不超过三秒钟！于是俺针对俺的代码开始了艰苦的优化工作，希\r\n";
m_Text+="望能达到甚至超过这一水平。一周之后1024位密钥的平均生成时间已经降至5 秒左\r\n";
m_Text+="右，但是单单依靠优化代码来进一步提高速度也非常困难了。于是俺开始借助金山\r\n";
m_Text+="词霸来查阅能够通过google找到的一切与RSA 算法相关的论文，但是网上关于RSA\r\n";
m_Text+="算法的论述绝大多数都是用于硬件实现的，将其算法流程用软件设计语言来实现极\r\n";
m_Text+="其繁琐。而且俺发现这样做下去俺只会离自己的初衷越来越远：俺的代码将不再清\r\n";
m_Text+="晰易懂。所以俺一度准备放弃。\r\n\r\n";
m_Text+=" 准备放弃之后，心态平静了许多，再回头去看那些原来不太能够理解的RSA 算\r\n";
m_Text+="法原理，却发现其实也不是那么高深莫测，不急不躁地慢慢看，慢慢想，突然就一\r\n";
m_Text+="下子全明白了。一番改进之后，现在这个版本的函数库同样具有非常简单而清晰的\r\n";
m_Text+="结构，速度也不算慢，生成1024位的密钥在俺PIII 900的笔记本上平均耗时不超过\r\n";
m_Text+="两秒。程序使用C++ 编写，可在VC6.0 下直接编译通过，希望大家喜欢。如果发现\r\n";
m_Text+="Bug 或者有好的修改建议，俺将非常感谢您能够给俺一个Mail。\r\n\r\n";
m_Text+=" 最后，感谢看雪论坛，感谢雪兄多次热心相助，俺在此学到了很多知识，当然\r\n";
m_Text+="还要乘机拍拍马屁，感谢俺家甜甜的支持！\r\n\r\n afanty@vip.sina.com";
m_Edit.SetWindowText(m_Text);
break;
case 1:
m_Text="";
m_Text+="RSA 原理：\r\n\r\n";
m_Text+="选取两个不同的大素数p、q，并计算N=p*q\r\n";
m_Text+="选取小素数d，并计算e，使d*e % (p-1)(q-1)=1\r\n\r\n";
m_Text+="对于任意A<N：\r\n\r\n";
m_Text+="若B=A**d % N\r\n";
m_Text+="则A=B**e % N\r\n\r\n";
m_Text+="可见d、e形成了非对称秘钥关系，加密者用公钥d加密，解密者可用私钥e解密，第\r\n";
m_Text+="三者即使拦截了密文B、公钥d和N，在不知道p、q的前提下，无法推算出e，从而无\r\n";
m_Text+="法获得明文A。当N取非常大的值时，将其因式分解成p、q是非常困难的，例如当N\r\n";
m_Text+="为1024 bit时，据分析，需动用价值数千万美金的大型计算机系统并耗费一年的时\r\n";
m_Text+="间。\r\n\r\n";
m_Text+="RSA 密钥的选取和加解密过程都非常简洁，在算法上主要要实现四个问题：\r\n\r\n";
m_Text+="1、如何处理大数运算\r\n";
m_Text+="2、如何求解同余方程 XY % M = 1\r\n";
m_Text+="3、如何快速进行模幂运算\r\n";
m_Text+="4、如何获取大素数\r\n\r\n";
m_Text+="实际上，在实现RSA 算法的过程中大家会发现后三个问题不是各自独立的，它们互\r\n";
m_Text+="有关联，环环相套，相信届时你会意识到：RSA算法是一种“优美”的算法！";
m_Edit.SetWindowText(m_Text);
break;
case 2:
m_Text="";
m_Text+=" RSA 依赖大数运算，目前主流RSA 算法都建立在1024位的大数运算之上。而大\r\n";
m_Text+="多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小于\r\n";
m_Text+="等于64位，即：0xffffffffffffffff，也就是18446744073709551615，这远远达不\r\n";
m_Text+="到RSA 的需要，于是需要专门建立大数运算库来解决这一问题。\r\n\r\n";
m_Text+=" 最简单的办法是将大数当作数组进行处理，数组的各元素也就是大数每一位上\r\n";
m_Text+="的数字，通常采用最容易理解的十进制数字0—9。然后对“数字数组”编写加减乘\r\n";
m_Text+="除函数。但是这样做效率很低，因为二进制为1024位的大数在十进制下也有三百多\r\n";
m_Text+="位，对于任何一种运算，都需要在两个有数百个元素的数组空间上多次重循环，还\r\n";
m_Text+="需要许多额外的空间存放计算的进退位标志及中间结果。另外，对于某些特殊的运\r\n";
m_Text+="算而言，采用二进制会使计算过程大大简化，而这种大数表示方法转化成二进制显\r\n";
m_Text+="然非常麻烦，所以在某些实例中则干脆采用了二进制数组的方法来记录大数，当然\r\n";
m_Text+="这样效率就更低了。\r\n\r\n";
m_Text+=" 一个有效的改进方法是将大数表示为一个n 进制数组，对于目前的32位系统而\r\n";
m_Text+="言n 可以取值为2 的32次方，即 0x100000000，假如将一个二进制为1024位的大数\r\n";
m_Text+="转化成0x10000000进制，就变成了32位，而每一位的取值范围不再是二进制的0—1\r\n";
m_Text+="或十进制的0—9，而是0-0xffffffff，我们正好可以用一个32位的DWORD （如：无\r\n";
m_Text+="符号长整数，unsigned long） 类型来表示该值。所以1024位的大数就变成一个含\r\n";
m_Text+="有32个元素的 DWORD数组，而针对 DWORD数组进行各种运算所需的循环规模至多32\r\n";
m_Text+="次而已。而且0x100000000 进制与二进制，对于计算机来说，几乎是一回事，转换\r\n";
m_Text+="非常容易。\r\n\r\n";
m_Text+=" 例如大数18446744073709551615，等于 0xffffffff ffffffff，就相当于十进\r\n";
m_Text+="制的99：有两位，每位都是0xffffffff。而18446744073709551616等于0x00000001\r\n";
m_Text+="00000000 00000000，就相当于十进制的100：有三位，第一位是1 ，其它两位都是\r\n";
m_Text+="0 ，如此等等。在实际应用中，“数字数组”的排列顺序采用低位在前高位在后的\r\n";
m_Text+="方式，这样，大数A 就可以方便地用数学表达式来表示其值：\r\n\r\n";
m_Text+="A=Sum[i=0 to n](A[i]*r**i)，r=0x100000000，0<=A[i]<r\r\n";
m_Text+="其中Sum 表示求和，A[i]表示用以记录A 的数组的第i 个元素，**表示乘方。\r\n\r\n";
m_Text+=" 任何整数运算最终都能分解成数字与数字之间的运算，在0x100000000 进制下\r\n";
m_Text+="其“数字”最大达到0xffffffff，其数字与数字之间的运算，结果也必然超出了目\r\n";
m_Text+="前32位系统的字长。在VC++中，存在一个__int64 类型可以处理64位的整数，所以\r\n";
m_Text+="不用担心这一问题，而在其它编译系统中如果不存在64位整形，就需要采用更小的\r\n";
m_Text+="进制方式来存储大数，例如16位的WORD类型可以用来表示0x10000 进制。但效率更\r\n";
m_Text+="高的办法还是采用32位的 DWORD类型，只不过将0x100000000 进制改成0x40000000\r\n";
m_Text+="进制，这样两个数字进行四则运算的最大结果为 0x3fffffff * 0x3fffffff，小于\r\n";
m_Text+="0xffffffffffffff，可以用一个双精度浮点类型（double，52位有效数字）来储存\r\n";
m_Text+="这一中间结果，只是不能简单地用高位低位来将中间结果拆分成两个“数字”。";
m_Edit.SetWindowText(m_Text);
break;
case 3:
m_Text="";
m_Text+="设有大数A、B和C，其中A>=B：\r\n\r\n";
m_Text+="A=Sum[i=0 to p](A[i]*r**i)\r\n";
m_Text+="B=Sum[i=0 to q](B[i]*r**i)\r\n";
m_Text+="C=Sum[i=0 to n](C[i]*r**i)\r\n";
m_Text+="r=0x100000000，0<=A[i],B[i],C[i]<r，p>=q\r\n\r\n";
m_Text+="则当C=A+B、C=A-B、C=A*B时，我们都可以通过计算出C[i]来获得C：\r\n\r\n\r\n";
m_Text+="C=A+B，显然C[i]不总是等于A[i]+B[i]，因为A[i]+B[i]可能>0xffffffff，而C[i]\r\n";
m_Text+="必须<=0xffffffff，这时就需要进位，当然在计算C[i-1]时也可能产生了进位，所\r\n";
m_Text+="以计算C[i]时还要加上上次的进位值。如果用一个64位变量result来记录和，另一\r\n";
m_Text+="个32位变量carry来记录进位，则有：\r\n\r\n";
m_Text+=" carry=0\r\n";
m_Text+=" FOR i FROM 0 TO p\r\n";
m_Text+=" result=A[i]+B[i]+carry\r\n";
m_Text+=" C[i]=result%0x100000000\r\n";
m_Text+=" carry=result/0x100000000\r\n";
m_Text+=" IF carry=0 n=p\r\n";
m_Text+=" ELSE n=p+1\r\n\r\n\r\n";
m_Text+="C=A-B，同理C[i]不总是等于A[i]-B[i]，因为A[i]-B[i]可能<0，而C[i]必须>=0，\r\n";
m_Text+="这时就需要借位，同样在计算C[i-1]时也可能产生了借位，所以计算C[i]时还要减\r\n";
m_Text+="去上次的借位值：\r\n\r\n";
m_Text+=" carry=0\r\n";
m_Text+=" FOR i FROM 0 TO p\r\n";
m_Text+=" IF A[i]-B[i]-carry>=0\r\n";
m_Text+=" C[i]=A[i]-B[i]-carry\r\n";
m_Text+=" carry=0\r\n";
m_Text+=" ELSE\r\n";
m_Text+=" C[i]=0x100000000+A[i]-B[i]-carry\r\n";
m_Text+=" carry=1\r\n";
m_Text+=" n=p\r\n";
m_Text+=" WHILE C[n]=0 n=n-1\r\n\r\n\r\n";
m_Text+="C=A*B，首先我们需要观察日常做乘法所用的“竖式计算”过程：\r\n\r\n";
m_Text+=" A3 A2 A1 A0\r\n";
m_Text+="* B2 B1 B0\r\n";
m_Text+="-------------------------------\r\n";
m_Text+="= A3B0 A2B0 A1B0 A0B0\r\n";
m_Text+="+ A3B1 A2B1 A1B1 A0B1\r\n";
m_Text+="+ A3B2 A2B2 A1B2 A0B2\r\n";
m_Text+="-------------------------------\r\n";
m_Text+="= C5 C4 C3 C2 C1 C0\r\n\r\n";
m_Text+="可以归纳出：C[i]=Sum[j=0 to q](A[i-j]*B[j])，其中i-j必须>=0且<=p。当然这\r\n";
m_Text+="一结论没有考虑进位，虽然计算A[i-j]*B[j]和Sum的时候都可能发生进位，但显然\r\n";
m_Text+="这两种原因产生的进位可以累加成一个进位值。最终可用如下算法完成乘法：\r\n\r\n";
m_Text+=" n=p+q-1\r\n";
m_Text+=" carry=0\r\n";
m_Text+=" For i FROM 0 TO n\r\n";
m_Text+=" result=carry\r\n";
m_Text+=" For j FROM 0 TO q\r\n";
m_Text+=" IF 0<=i-j<=p result=result+A[i-j]*B[j]\r\n";
m_Text+=" C[i]=result%0x100000000\r\n";
m_Text+=" carry=result/0x100000000\r\n";
m_Text+=" IF carry!=0\r\n";
m_Text+=" n=n+1\r\n";
m_Text+=" C[n]=carry\r\n\r\n\r\n";
m_Text+="对于C=A/B，由于无法将B 对A“试商”，我们只能转换成B[q]对A[p]的试商来得到\r\n";
m_Text+="一个近似值，所以无法直接通过计算C[i]来获得C，只能一步步逼近C。由于：\r\n\r\n";
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -