DELPHI盒子
!实时搜索: 盒子论坛 | 注册用户 | 修改信息 | 退出
检举帖 | 全文检索 | 关闭广告 | 捐赠
技术论坛
 用户名
 密  码
自动登陆(30天有效)
忘了密码
≡技术区≡
DELPHI技术
移动应用开发
Web应用开发
数据库专区
报表专区
网络通讯
开源项目
论坛精华贴
≡发布区≡
发布代码
发布控件
文档资料
经典工具
≡事务区≡
网站意见
盒子之家
招聘应聘
信息交换
论坛信息
最新加入: steven7890
今日帖子: 8
在线用户: 23
导航: 论坛 -> DELPHI技术 斑竹:liumazi,sephil  
作者:
男 reniastyc (天道玄虚) ▲▲△△△ -
注册会员
2021/1/29 22:19:07
标题:
「FireMonkey」「重复造轮子」用Delphi实现大数运算及RSA加密 浏览:964
加入我的收藏
楼主: 虽说通常情况下不必重复造轮子,但对于个人而言,重复造轮子其实是一个很好的学习和提高的过程。至少在对于算法的理解方面,重复造过轮子之后,相关算法的理解程度必定能够有所提高。
这次重复造的轮子是大数运算和RSA加密,源码见:https://github.com/Reniastyc/SimpleRSA

开发平台:Delphi 10.4.1
架构:FireMonkey

首先,简单介绍一下算法中所用大数的结构。

TLongInteger = class
{前略}
    FSymb: Boolean;
    FNumL: TArray<Boolean>;
{后略}
end;

使用FSymb记录符号,FNumL以二进制记录大数的内容。之所以选择二进制而非其他进制,主要是因为在位运算等方面,2进制自有其方便和优势所在。
四则运算方面,加减法使用逻辑运算实现:

加法(前后略):
    FNumL[i] := X xor Y xor C;
    C := (X and Y) or (C and (X or Y));
减法(前后略):
    FNumL[i] := X xor Y xor C;
    C := (Y and C) or ((not X) and (Y or C))

乘法使用快速傅利叶变换,除法则基于减法实现。
为了实现乘法中用到的快速傅利叶变换,我并没有使用Delphi提供的复数类,而是建立了两个分别基于模-辐角和实部-虚部的复数结构,并写了一个相互的转换函数(前后略):

  TComplexMA = record
    FM: Double;
    FA: Double;
  end;

  TComplexRI = record
    FR: Double;
    FI: Double;
  end;

之所以作这样的处理,是因为模-辐角表示法更适合乘除运算(每次乘法运算仅仅需要一次乘法和一次加减即可,除法亦然),而实部-虚部表示法则更适用于加减运算。由于在傅利叶变换的核心部份,存在连续的加减或连续的乘除步骤,每次转换后节省的时间都要比不转换而直接运算耗费的时间更多。实测表明,计算效率的确有所提升(大约5%-11%)。

素数运算方面,使用米勒-拉宾算法进行素性检验,目前个人测试的情况下,还没有遇见生成的素数无法进行RSA加密及解密的情况。在I7-6700HQCPU下进行单核运算,生成十个256位二进制素数用时239140ms

发布的RSA加密器可以在上述Github网址下载,源码也在其中提供。
虽然大概不具有实用的加密性能,唯希望能为想要研究这一方面的朋友提供一点微不足道的参考。
----------------------------------------------
--O, ye Magnificient Deity's Miracle!
--I'm yet Reniastyc de El Magnifico.
作者:
男 reniastyc (天道玄虚) ▲▲△△△ -
注册会员
2021/1/29 22:20:26
1楼: 上文所说生成10个256位2进制素数用时,有图为证
此帖子包含附件:
PNG 图像
大小:13.0K
----------------------------------------------
--O, ye Magnificient Deity's Miracle!
--I'm yet Reniastyc de El Magnifico.
作者:
男 keymark (keymark) ▲▲△△△ -
注册会员
2021/1/29 22:43:58
2楼: Crypt::OpenSSL
EVP
github上有Delphi调用的pas约定 demo(这玩意挺多的)按此在新窗口浏览图片
中文的
----------------------------------------------
播客
作者:
男 datm (dATM) ★☆☆☆☆ -
盒子活跃会员
2021/1/29 22:44:38
2楼: 厉害
----------------------------------------------
-
作者:
男 bbnn38 (伟大的咸鱼) ▲▲▲▲△ -
注册会员
2021/1/29 23:26:26
3楼: 运气好,一上来就看到好东西
----------------------------------------------
-
作者:
男 bbnn38 (伟大的咸鱼) ▲▲▲▲△ -
注册会员
2021/1/29 23:53:23
4楼: 测试了一下演示程序,用123123这组文字选择“字符串加密成字符串”后再“字符串解密成字符串”只剩下12312了,再次重复加密解密就剩下1231了 每次少一位字符
----------------------------------------------
-
作者:
男 reniastyc (天道玄虚) ▲▲△△△ -
注册会员
2021/1/30 9:20:52
5楼: 感谢测试,我研究一下
----------------------------------------------
--O, ye Magnificient Deity's Miracle!
--I'm yet Reniastyc de El Magnifico.
作者:
男 reniastyc (天道玄虚) ▲▲△△△ -
注册会员
2021/1/30 9:35:14
6楼: 因为未知原因会丢一个尾字符,所以在读入的时候在尾端加一个空格就好了。
但神奇的地方在于,我测试的时候字符串居然没试过纯数字,用中文字符测试没遇见这问题,就很神奇。
https://github.com/Reniastyc/SimpleRSA/releases/tag/v1.21fix
此帖子包含附件:reniastyc_20211309355.zip 大小:3.41M
----------------------------------------------
--O, ye Magnificient Deity's Miracle!
--I'm yet Reniastyc de El Magnifico.
作者:
男 bbnn38 (伟大的咸鱼) ▲▲▲▲△ -
注册会员
2021/2/3 0:01:44
7楼: 大概猜测了一下是Normalize导致了123 这样的字符消失,因为123字符是 $31 $00 $32 $00 $33 $00 你这个Normalize函数会把最后面的$00去掉,导致变成了$31 $00 $32 $00 $33,作者能否修复修复修复?
现在我临时解决方法是下面这样的,暂时凑合用。
此帖子包含附件:
PNG 图像
大小:83.7K
----------------------------------------------
-
作者:
男 reniastyc (天道玄虚) ▲▲△△△ -
注册会员
2021/2/3 9:30:19
8楼: 多谢指点,看来的确需要调整。因为转换为大数的时候,序列后方的数会被作为大数的首数,Normalize会把起始的零去掉以保证这不是一个以零为起始的数。
上方提供的方案的确正好能解决这一问题。
再次感谢
----------------------------------------------
--O, ye Magnificient Deity's Miracle!
--I'm yet Reniastyc de El Magnifico.
作者:
男 reniastyc (天道玄虚) ▲▲△△△ -
注册会员
2021/2/3 9:36:00
9楼: procedure TRSATest.Button5Click(Sender: TObject);
var
  BS: TBytes;
begin
  if Memo1.Text = '' then
  begin
    Exit;
  end;
  case ComboBox1.ItemIndex of
    0: RSATE.FromString16(Memo1.Text.Replace(sLineBreak, ''));
    1: RSATE.FromString10(Memo1.Text.Replace(sLineBreak, ''));
    2: RSATE.FromBytes(WideBytesof(Memo1.Text));
  else
    Exit;
  end;
  if RSATE.LessThan(RSAN) and not RSAE.IsZero then
  begin
    RSATE.PowAndMod(RSAE, RSAN);
    case ComboBox2.ItemIndex of
      0: Memo1.Text := RSATE.ToString16;
      1: Memo1.Text := RSATE.ToString10;
      2:
      begin
        BS := RSATE.ToBytes;
        if Length(BS) and 1 <> 0 then
        begin
          SetLength(BS, Length(BS) + 1);
          BS[Length(BS) - 1] := 0;
        end;
        Memo1.Text := WideStringOf(BS);
      end;
    else
      Exit;
    end;
  end;
end;

procedure TRSATest.Button6Click(Sender: TObject);
var
  BS: TBytes;
begin
  if Memo1.Text = '' then
  begin
    Exit;
  end;
  case ComboBox3.ItemIndex of
    0: RSATE.FromString16(Memo1.Text.Replace(sLineBreak, ''));
    1: RSATE.FromString10(Memo1.Text.Replace(sLineBreak, ''));
    2: RSATE.FromBytes(WideBytesof(Memo1.Text));
  else
    Exit;
  end;
  if RSATE.LessThan(RSAN) and not RSAD.IsZero then
  begin
    RSATE.PowAndMod(RSAD, RSAN);
    case ComboBox4.ItemIndex of
      0: Memo1.Text := RSATE.ToString16;
      1: Memo1.Text := RSATE.ToString10;
      2:
      begin
        BS := RSATE.ToBytes;
        if Length(BS) and 1 <> 0 then
        begin
          SetLength(BS, Length(BS) + 1);
          BS[Length(BS) - 1] := 0;
        end;
        Memo1.Text := WideStringOf(BS);
      end;
    else
      Exit;
    end;
  end;
end;
此帖子包含附件:reniastyc_20212394721.zip 大小:3.41M
----------------------------------------------
--O, ye Magnificient Deity's Miracle!
--I'm yet Reniastyc de El Magnifico.
作者:
男 cnpack (CnPack) ★☆☆☆☆ -
普通会员
2021/2/3 11:23:23
10楼: CnPack组件包中也有纯Pascal实现的RSA加解密代码,示例见 cnvcl\Examples\RSA
开源地址:
https://github.com/cnpack/cnvcl.git

有种说法说用浮点做快速傅里叶变换有可能因为浮点误差导致计算结果有偏差(还没有碰到过),推荐改用快速数论变换。但我们还没有研究过。
----------------------------------------------
欢迎使用CnPack IDE Wizards
http://www.cnpack.org/
作者:
男 wang_80919 (Flying Wang) ▲▲▲▲▲ -
普通会员
2021/2/3 11:30:40
11楼: 请问 楼上高手 
cnvcl 里的 加密解密 啥时候 支持 TBYTES 和 TENCODING ?
----------------------------------------------
(C)(P)Flying Wang
作者:
男 lordaeron (Terry) ★☆☆☆☆ -
注册会员
2021/2/3 14:22:13
12楼: 大數運算,最重要快的是power module.
----------------------------------------------
-
作者:
男 reniastyc (天道玄虚) ▲▲△△△ -
注册会员
2021/2/6 13:23:58
13楼: 回复楼上,经过实测之后确认,目前我所使用的快速傅立叶变换没有实用上的误差,反正是快速数论变换不论是在支持的位数上,还是总体效率上,都有所欠缺。

至于复数浮点运算带来的效率问题,实测分别使用两种复数构成法可以有效缓解。

另外,我所设计的这一手RSA,目前已经能够对文件进行分割加密。

具体来说,假如你用的密钥,模数占511位,64字节不到,则会将待加密的文件按63字节分割,以确保每一段都小于模数,并将加密结果按64字节填充以确保不会溢出。经过调整后,应该能够确保加密的正确性。(使用添加文件尾端的方法避免了尾端为0时带来的丢失,这一点要感谢bbnn38在一开始的指出和帮助)

而这一加密手段能够经过微调后直接用于对TBytes的加密,你衹需要使用内置的TInteger.FromBytes即可将TBytes转为TLongInteger,然后即可利用内建的运算了。

PowerMod优化方面,目前暂时没有更好的想法,如愿指教,感激不尽。

你可以在Github上下载最新的源码和加密器,目前版本为1.23Fix,已经支持文件加密https://github.com/Reniastyc/SimpleRSA

也可以直接在附件中下载加密器。
此帖子包含附件:reniastyc_202126132347.zip 大小:3.66M
----------------------------------------------
--O, ye Magnificient Deity's Miracle!
--I'm yet Reniastyc de El Magnifico.
作者:
男 crystalmoon (crystalmoon) ★☆☆☆☆ -
盒子活跃会员
2021/2/7 8:39:21
14楼: 佩服楼主的研究精神。。。我看见数学就头疼。。。按此在新窗口浏览图片
----------------------------------------------
-
作者:
男 cnpack (CnPack) ★☆☆☆☆ -
普通会员
2021/2/7 10:04:15
15楼: 11楼,我记得Tbytes支持早就加了。按此在新窗口浏览图片
----------------------------------------------
欢迎使用CnPack IDE Wizards
http://www.cnpack.org/
作者:
男 lordaeron (Terry) ★☆☆☆☆ -
注册会员
2021/2/8 9:40:39
16楼: montgomery or fast hartley transform
github 上有一位PORT C# 的TINTX, 我的REPO 上留一份並在應用上修了一點。它是 fast hartley transform

montgomery 比較好找,github 上一堆。

power module 基本上四則都用上了。
要測一個big integer 快不快,用這個就很省事。
----------------------------------------------
-
作者:
男 lordaeron (Terry) ★☆☆☆☆ -
注册会员
2021/2/8 9:54:11
17楼: Big integer 的lib 的頂尖高手為 GMP,這個不用跟它比的了。
TINTX 應用在ANDROID 上,就算是ANDROID 8/9 的機子,
跑一個SSH 的power module 都要快1 分鐘算才出來。
純PASCAL 真的快不了。
晚些再PO 出我的測資。
----------------------------------------------
-
作者:
男 reniastyc (天道玄虚) ▲▲△△△ -
注册会员
2021/2/9 10:25:23
18楼: 勞煩樓上幫忙測試了
----------------------------------------------
--O, ye Magnificient Deity's Miracle!
--I'm yet Reniastyc de El Magnifico.
作者:
男 lordaeron (Terry) ★☆☆☆☆ -
注册会员
2021/2/9 21:02:01
19楼: writeln(stdout,'SIMPLE RSA START');
NTickInitial:= GetTickCount64;
lf := TLongInteger.Create;
lx := TLongInteger.Create;
lp := TLongInteger.Create;
lk := TLongInteger.Create;
lf.FromString16('BDB1DF76C754F735AA3399B2E9B86523'+
'20BA60999D8EF284DEEBF9267FC197A7'+
'37E9AA7D7C83813CBC9022E02FFB36D3'+
'5EB0E513AEFE3656577E53D23D906D0D'+
'49CE23E3D9E87AA6A0D1E41FBEC29158'+
'0567F2ACB576D52ECE8DE3F9413D3590'+
'DBD151432893F0AA6CF670EFE9507448'+
'7AA92A1A4D9DF0AF9402C1C06AF97849'+
'2B493F30F854C3D6F22C5ABF520E0A0B'+
'C3926EAFF062534D8ADC05F0DD06BF79'+
'838F16019164FBF971EC1E04F37F910A'+
'1CD554615217C8FEE652D1B4ED2E67AB'+
'7366CBA81AC7C612F0004953F9ABE691'+
'EBDFEB1C4A598D50FBD4B31DB7957F9B'+
'C7CDD320125F6266BDB4CE9B4C3256AD'+
'124CFAD5ADB1A7BF6FB9A3F6DD3FCF1B');
lx.FromString16('AEDC0E7A72E3B4AE30C6CCDE94575E40'+
'CCC604A846CA99554A4531AB8D26CADB'+
'546FB3190B907379321EE17CA9EBA957'+
'8DCDEBF3B4A87EE95E057C2F9C82F770'+
'344972C1F714121959BD7D6605B8253D'+
'79EDD8C912147D16A77516EBFE387B81'+
'3123499DAFC559F48DA289BFE8532BA5'+
'C1C83BD1B38373F97F8C81C07A79ABFC');
lp.FromString16('FFFFFFFFFFC90FDAA22168C234'+
'C4C6628B80DC1CD129024E088A67CC74'+
'020BBEA63B139B22514A08798E3404DD'+
'EF9519B3CD3A431B302B0A6DF25F1437'+
'4FE1356D6D51C245E485B576625E7EC6'+
'F44C42E9A637ED6B0BFF5CB6F406B7ED'+
'EE386BFB5A899FA5AE9F24117C4B1FE6'+
'49286651ECE45B3DC2007CB8A163BF05'+
'98DA48361C55D39A69163FA8FD24CF5F'+
'83655D23DCA3AD961C62F356208552BB'+
'9ED529077096966D670C354E4ABC9804'+
'F1746C08CA18217C32905E462E36CE3B'+
'E39E772C180E86039B2783A2EC07A28F'+
'B5C55DF06F4C52C9DE2BCBF695581718'+
'3995497CEA956AE515D2261898FA0510'+
'15728E5A8AACAA68FFFFFFFFFF');
//K = f^x mod p
lk:=lf.PowAndMod(lx,lp);
NTickShowEnd:= GetTickCount64;
writeln(StdOut,Format('SIMPRSA: finished: %dms', [(NTickShowEnd-NTickInitial)]));
writeln(stdout,lk.ToString10); 

答案:
7587763945179871941269354864943492315282302613655809192407236739172754025648197263841893434139825106133993891144992524411715019043777509242103077895825857844290221069284061399909284352989861703858974086465347607641043807549041102707159145588502451132969651600427709088295374175283565289803711057791660170982626754188967998185765813362636488306374446514746053906647207156471549348613386856310553486156282874263832564754569702918504609882508593840983642372662027250571274469469178835631727328877370847714491019865380844427507030993909066791574430382955002068156955237101531657497941376479788152319646413375838997709735

SIMPRSA: 51766ms

對照其它IMPLEMENTATION, 
用JAVA 的BIGINTEGER 跑31ms
TINTX 跑16~31ms
TBigInteger: 15ms

慢得離普了。
----------------------------------------------
-
作者:
男 hawke2e (hawke2e) ▲▲▲▲▲ -
注册会员
2021/2/9 22:37:54
20楼: 有学习研究精神是好事。
就是觉得楼主的称呼,跟公司的名字起得比较虚的那些类似,比如:玄武。  不大妥当,不知怎么说。
因为我们日常面对的事情绝大多数属于可计算的,简单来说就是只要你肯花时间,基本上没有你弄不懂的事情。
如果有,那多半有忽悠的成份。比如:玄、虚,何谓玄何谓虚?
天道,虽然种种迹象表明所有客观规律可能都来自一个“根本”规律,但这规律不见得人类能认识和理解。像《道德经》那个也只能用来帮助人思考,不能作为“根本”的客观规律。
在中国传统文化里,比较虚又很优秀的文化,我觉得只有中医。
厉害的中医师能看出人差不多要SI,但没有一个西医能做到,西医只能看着病情预测其寿命,但自然SI亡是预测不了的,中医可以。
水平高的中医师可以领导一个团队的西医,但西医水平再高都领导不了一群中医,这是个挺有趣的现象。

另外,我觉得“字节跳动”这公司名字起得相当的好,好到我还想不出比它更好的名字。
----------------------------------------------
软件是什么,相信很多人都说不清。
作者:
男 reniastyc (天道玄虚) ▲▲△△△ -
注册会员
2021/2/10 13:12:11
21楼: 請問Terry,您瞭解甚麼好用的優化手段嗎?
在下衹是這方面的較初學者,故並無足夠的造詣。如願重點,感激不盡。
----------------------------------------------
--O, ye Magnificient Deity's Miracle!
--I'm yet Reniastyc de El Magnifico.
作者:
男 lordaeron (Terry) ★☆☆☆☆ -
注册会员
2021/2/10 20:01:42
22楼: 沒多花時間看你的CODE, 只是將它放到FPC 上和我手上其它的一起測而已。
Big Integer 上沒絕對好的算法,每種都有它的位數的適性。
BUT 看你的說明, 我直覺是你用BOOLEAN 的關係比較大。
這東西,對MEMORY ACCESS 的影響大。
理應是對應64bit 或32 bit 的來處理。
用BOOLEAN 來處理,真的不在我的想像中。
----------------------------------------------
-
作者:
男 lordaeron (Terry) ★☆☆☆☆ -
注册会员
2021/2/10 20:07:31
23楼: 參考https://www.bearssl.org/bigint.html
OR
FFT-Based McLaughlin's Montgomery Exponentiation without Conditional Selections
OR
https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
----------------------------------------------
-
作者:
男 reniastyc (天道玄虚) ▲▲△△△ -
注册会员
2021/2/12 9:56:33
24楼: 感謝樓上,那我先改用Byte作爲基準重新寫一下試試看。
----------------------------------------------
--O, ye Magnificient Deity's Miracle!
--I'm yet Reniastyc de El Magnifico.
作者:
男 keymark (keymark) ▲▲△△△ -
注册会员
2021/2/12 10:41:56
25楼: https://www.bearssl.org/gitweb/?p=BearSSL;a=tree;f=src/int;h=2fa2ff106f0cf006b83e705855c2f85bf7d76ece;hb=8ef7680081c61b486622f2d983c0d3d21e83caad
按此在新窗口浏览图片
可以抄。哈哈
----------------------------------------------
播客
作者:
男 lordaeron (Terry) ★☆☆☆☆ -
注册会员
2021/2/12 12:21:47
26楼: bearssl 是C 寫的,要抄就要看對C 的了解了。
原PO 就是想要挑戰硬體的定義?
如果你不明白為何INT32 或 INT64 會比較快, 哪你最好了解一下STRUCTURE/RECORD 為何需要ALIGN。
----------------------------------------------
-
作者:
男 cnpack (CnPack) ★☆☆☆☆ -
普通会员
2021/2/14 11:28:21
27楼: 符号用Boolean和Byte甚至DWORD的区别应该不大,即使有对齐的影响造成重复访存,也只影响TArray一处引用,不影响TArray内部的所有内容。

耗时具体在什么地方可以用AQTime之类的工具来记录分析一下。

没仔细看代码,猜一猜可能的问题,一是class类型的导致反复Create和Free有一定耗时,一是PowerMod采用蒙哥马利法变MulMod,会不会MulMod又继续优化成AddMod了?
----------------------------------------------
欢迎使用CnPack IDE Wizards
http://www.cnpack.org/
信息
登陆以后才能回复
Copyright © 2CCC.Com 盒子论坛 v2.1 版权所有 页面执行35.15625毫秒 RSS