📄 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 = 1;
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 = 0;
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);
TreeCtrlItem.hParent = hTreeItem1;
TreeCtrlItem.item.pszText = _T("幂模运算");
TreeCtrlItem.item.lParam = 9;
m_Tree.InsertItem(&TreeCtrlItem);
TreeCtrlItem.hParent = hTreeItem1;
TreeCtrlItem.item.pszText = _T("素数测试");
TreeCtrlItem.item.lParam = 10;
m_Tree.InsertItem(&TreeCtrlItem);
TreeCtrlItem.hParent = hTreeItem1;
TreeCtrlItem.item.pszText = _T("输入输出");
TreeCtrlItem.item.lParam = 11;
m_Tree.InsertItem(&TreeCtrlItem);
return TRUE;
}
void CHelpDlg::OnSelchangedTree(NMHDR* pNMHDR, LRESULT* pResult)
{
NM_TREEVIEW* pNMTreeView = (NM_TREEVIEW*)pNMHDR;
switch(pNMTreeView->itemNew.lParam)
{
case 0:
break;
case 1:
m_Text="";
m_Text+="\r\n";
m_Text+=" 俺曾经查阅了网上找得到的各种用于实现RSA 的大数运算库，然而最终还是决定";
m_Text+="\r\n";
m_Text+="自己动手写一个。因为凡是效率高速度快的代码，如 crypto++、miracl、freelip、";
m_Text+="\r\n";
m_Text+="rsaref等，要么使用的算法过于复杂，要么编码风格杂乱无章，俺的水平和耐心都实";
m_Text+="\r\n";
m_Text+="在是有限，以至于无法读懂这些东西。而俺读得懂的一些代码，其实现方式却又过于";
m_Text+="\r\n";
m_Text+="幼稚，效率极低速度一塌糊涂。俺想象俺这样的人不在少数，于是决心做一个清晰易";
m_Text+="\r\n";
m_Text+="懂，效率也过得去的东西奉献给大家。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 这个函数库刚做好的时候，生成1024位的随机密钥耗时大约5 分钟，俺认为是可";
m_Text+="\r\n";
m_Text+="以接受的。但后来找到一个叫tE! 的老外用miracl库写的RsaTools，发现其生成1024";
m_Text+="\r\n";
m_Text+="位的密钥耗时不超过三秒钟！于是俺针对俺的代码开始了艰苦的优化工作，希望能达";
m_Text+="\r\n";
m_Text+="到甚至超过这一水平。一周之后1024位密钥的平均生成时间已经降至5 秒以内，但是";
m_Text+="\r\n";
m_Text+="单单依靠优化代码来进一步提高速度也非常困难了。于是俺开始借助金山词霸来查阅";
m_Text+="\r\n";
m_Text+="能够通过google找到的一切与Rsa 算法相关的论文，直到今天俺决定放弃，因为俺发";
m_Text+="\r\n";
m_Text+="现在改用越来越复杂的数学算法的同时俺离自己的初衷也越来越远：俺的代码也不再";
m_Text+="\r\n";
m_Text+="清晰易懂了。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 现在这个版本的函数库采用了最简单的结构和最容易理解的算法，速度也不算太";
m_Text+="\r\n";
m_Text+="慢，用C++ 语言，可在VC6.0 下直接编译通过，希望大家喜欢。如果发现Bug 或者有";
m_Text+="\r\n";
m_Text+="好的修改建议，俺将非常感谢您能够给俺一个Mail。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 最后，感谢看雪论坛，俺在此学到了很多知识，也要感谢雪兄多次热心相助，当";
m_Text+="\r\n";
m_Text+="然还要乘机拍拍马屁，感谢俺家甜甜的支持！";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" afanty@vip.sina.com";
m_Edit.SetWindowText(m_Text);
break;
case 2:
m_Text="";
m_Text+="\r\n";
m_Text+=" RSA 依赖大数运算，目前主流RSA 算法都建立在512 到1024位的大数运算之上。";
m_Text+="\r\n";
m_Text+="而大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小";
m_Text+="\r\n";
m_Text+="于等于64位，即：0xffffffffffffffff，也就是18446744073709551615，这远远达不";
m_Text+="\r\n";
m_Text+="到RSA 的需要，于是需要专门建立大数运算库来解决这一问题。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 最简单的办法是将大数当作数组进行处理，也就是将大数用0—9这十个数字组成";
m_Text+="\r\n";
m_Text+="的数组进行表示，然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。";
m_Text+="\r\n";
m_Text+="但是这样做效率很低，因为二进制为1024位的大数其十进制也有三百多位，对于任何";
m_Text+="\r\n";
m_Text+="一种运算，都需要在两个有数百个元素的数组空间上做多重循环，还需要许多额外的";
m_Text+="\r\n";
m_Text+="空间存放计算的进退位标志及中间结果。另外，对于某些特殊的运算而言，采用二进";
m_Text+="\r\n";
m_Text+="制会使计算过程大大简化，这种大数表示方法转化成二进制显然非常麻烦，所以在某";
m_Text+="\r\n";
m_Text+="些实例中则干脆采用了二进制数组的方法来记录大数，这样效率就更低了。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 一个有效的改进方法是将大数表示为一个n 进制数组，对于目前的32位系统而言";
m_Text+="\r\n";
m_Text+="n 可以取值为2 的32次方，即0x10000000，假如将一个二进制为1024位的大数转化成";
m_Text+="\r\n";
m_Text+="0x10000000进制，它就变成了32位，而每一位的取值范围就不是二进制的0—1或十进";
m_Text+="\r\n";
m_Text+="制的0—9，而是0-0xffffffff，我们正好可以用一个无符号长整数来表示这一数值。";
m_Text+="\r\n";
m_Text+="所以1024位的大数就是一个有32个元素的unsigned long数组，针对unsigned long数";
m_Text+="\r\n";
m_Text+="组进行各种运算所需的循环规模至多32次而已。而且0x100000000 进制与二进制，对";
m_Text+="\r\n";
m_Text+="于计算机来说，几乎是一回事，转换非常容易。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 例如大数18446744073709551615，等于 ffffffff ffffffff，就相当于十进制的";
m_Text+="\r\n";
m_Text+="99：有两位，每位都是ffffffff。而18446744073709551616 等于00000001 00000000";
m_Text+="\r\n";
m_Text+="00000000，就相当于十进制的100：有三位，第一位是1 ，其它两位是0，如此等等。";
m_Text+="\r\n";
m_Text+="在实际应用中，“数字”数组的排列顺序采用低位在前高位在后的方式，这样，大数";
m_Text+="\r\n";
m_Text+="A 就可以方便地用数学表达式来表示其值：A=Sum[i=0 to n](A[i]*0x100000000**i)";
m_Text+="\r\n";
m_Text+="（其中Sum 表示求和，A[i]表示用以记录A 的数组的第i 个元素，**表示乘方）。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 任何整数运算最终都能分解成数字与数字之间的运算，在0x100000000 进制下其";
m_Text+="\r\n";
m_Text+="“数字”最大达到0xffffffff，其数字与数字之间的运算，结果也必然超出了目前32";
m_Text+="\r\n";
m_Text+="系统的字长。在VC++中，存在一个__int64 类型可以处理64位的整数，所以不用担心";
m_Text+="\r\n";
m_Text+="这一问题，而在其它编译系统中如果不存在64位整形，就需要采用更小的进制方式来";
m_Text+="\r\n";
m_Text+="存储大数，例如WORD类型（16位）可以用来表示0x10000 进制，但效率更高的办法还";
m_Text+="\r\n";
m_Text+="是采用32位的DWORD 类型，只不过将0x100000000 进制改成0x40000000进制，这样两";
m_Text+="\r\n";
m_Text+="个数字进行四则运算的最大结果为 0x3fffffff * 0x3fffffff，小于0xffffffff，只";
m_Text+="\r\n";
m_Text+="是不能简单地用高位低位来将运算结果拆分成两个“数字”。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Edit.SetWindowText(m_Text);
break;
case 3:
m_Text="";
m_Text+="\r\n";
m_Text+="设：";
m_Text+="\r\n";
m_Text+=" A=Sum[i=0 to p](A[i]*0x100000000**i)";
m_Text+="\r\n";
m_Text+=" B=Sum[i=0 to q](B[i]*0x100000000**i)，p>=q";
m_Text+="\r\n";
m_Text+=" C=Sum[i=0 to n](C[i]*0x100000000**i)=A+B";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="显然：";
m_Text+="\r\n";
m_Text+=" C[i]不是简单地等于A[i]+B[i]，因为如果C[i]>0xffffffff就需要进位，当然计算";
m_Text+="\r\n";
m_Text+=" C[i-1]时也可能产生了进位，所以计算C[i]时还要加上上次的进位值。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="如果用carry[i]记录每次的进位则有：";
m_Text+="\r\n";
m_Text+=" C[i]=A[i]+B[i]+carry[i-1]-carry[i]*0x100000000";
m_Text+="\r\n";
m_Text+=" 其中carry[-1]=0";
m_Text+="\r\n";
m_Text+=" 若A[i]+B[i]+carry[i-1]>0xffffffff，则carry[i]=1；反之则carry[i]=0";
m_Text+="\r\n";
m_Text+=" 若carry[p]=0，则n=p；反之则n=p+1";
m_Text+="\r\n";
m_Text+="\r\n";
m_Edit.SetWindowText(m_Text);
break;
case 4:
m_Text="";
m_Text+="\r\n";
m_Text+="设：";
m_Text+="\r\n";
m_Text+=" A=Sum[i=0 to p](A[i]*0x100000000**i)";
m_Text+="\r\n";
m_Text+=" B=Sum[i=0 to q](B[i]*0x100000000**i)，p>=q";
m_Text+="\r\n";
m_Text+=" C=Sum[i=0 to n](C[i]*0x100000000**i)=A-B";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="显然：";
m_Text+="\r\n";
m_Text+=" C[i]不是简单地等于A[i]-B[i]，因为如果A[i]<B[i]就需要借位，当然计算";
m_Text+="\r\n";
m_Text+=" C[i-1]时也可能产生了借位，所以计算C[i]时还要减去上次的借位值。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="如果用carry[i]记录每次的借位则有：";
m_Text+="\r\n";
m_Text+=" C[i]=A[i]+carry[i]*0x100000000-B[i]-carry[i-1]";
m_Text+="\r\n";
m_Text+=" 其中carry[-1]=0";
m_Text+="\r\n";
m_Text+=" 若A[i]>B[i]则carry[i]=0；反之则carry[i]=1";
m_Text+="\r\n";
m_Text+=" 若C[p]=0，则n=p-1；反之则n=p";
m_Text+="\r\n";
m_Text+="\r\n";
m_Edit.SetWindowText(m_Text);
break;
case 5:
m_Text="";
m_Text+="\r\n";
m_Text+="设：";
m_Text+="\r\n";
m_Text+=" A=Sum[i=0 to p](A[i]*0x100000000**i)";
m_Text+="\r\n";
m_Text+=" B=Sum[i=0 to q](B[i]*0x100000000**i)，p>=q";
m_Text+="\r\n";
m_Text+=" C=Sum[i=0 to n](C[i]*0x100000000**i)=A*B";
m_Text+="\r\n";
m_Text+="";
m_Text+="\r\n";
m_Text+="显然：";
m_Text+="\r\n";
m_Text+=" C=Sum[i=0 to q](A*B[i]*0x100000000**i)";
m_Text+="\r\n";
m_Text+=" 而(A*B[i]*100000000**i)=Sum[j=0 to p](A[j]*B[i]*0x100000000**(i+j))";
m_Text+="\r\n";
m_Text+=" 所以C=Sum[i=0 to q](Sum[j=0 to p](A[j]*B[i]*0x100000000**(i+j)))";
m_Text+="\r\n";
m_Text+="";
m_Text+="\r\n";
m_Text+="因此：";
m_Text+="\r\n";
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -