基于Montgomery算法的高速、可配置 RSA密码IP核硬件设计系列(二)——模乘模幂设计方案

已于 2022-06-20 11:33:50 修改
阅读量2.6k 收藏 22
点赞数 7
分类专栏： 数字硬件安全--精选 文章标签： 密码学 RSA 蒙哥马利模乘
于 2021-02-27 20:31:20 首次发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/vivid117/article/details/114189731
版权
本文是基于Montgomery算法的RSA密码IP核硬件设计系列的第二部分，主要讨论模乘和模幂的设计方案。模乘方案包括蒙哥马利模乘的原始算法、基2优化以及基16的高基模乘算法，通过流水线结构和特定的硬件乘法器提高运算速度。模幂方案探讨了L-R和R-L二进制算法，考虑了安全性与速度的平衡。

摘要生成于 C知道 ，由 DeepSeek-R1 满血版支持， 前往体验 >

基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列（二）


原创声明：本系列所有的博文都是本人参考相关的文献资料后，独立撰写，组织语言后，编写本系列博文，未经作者允许，严禁转载；

基于Montgomery算法的高速、可配置 RSA密码IP核硬件设计系列(二)
本次第二部分主要介绍相关项目的具体模块的设计方案，如模乘设计方案，模幂设计方案；

1.3 模乘算法设计方案

在2.3 节模幂算法方案中，所有的 RSA 模幂算法最终转换为：模乘运算和模平方运算，而模乘和模平方其实是相同的操作，即可以用公式 (5) 表示：
在这里插入图片描述

式中，X, Y, N 均是 k 比特位二进制大整数，对于模平方运算，使得 X = Y 即可。
因此可以通过同一硬件来完成，加解密的性能最终取决于模乘的速度。而模乘算法也是多种多样，各有利弊。其中最著名的实现大数模乘的算法，即由Peter L. Montgomery提出的蒙哥马利模乘算法 (Montgomery’s algorithm)。
蒙哥马利模乘算法得到的结果并不是公式 (5) 的结果，

了解本专栏 订阅专栏 解锁全文 超级会员免费看
基于Montgomery算法的高速、可配置 RSA密码IP核硬件设计系列(一)——总体方案设计
用心记录每天的学习，提升自己，虽然有的很基础但真的很重要！
02-27 2822
原创声明：本系列所有的博文都是本人参考相关的文献资料后，独立撰写，组织语言后，编写本系列博文，如需转载，请注明转载出处； 基于Montgomery算法的高速、可配置 RSA密码IP核硬件设计系列(一) 本次第一部分主要介绍相关项目的背景，意义，研究内容，以及总体的设计方案； 0. 前言 密码技术是当今保障信息安全的核心技术。作为公钥密码体制代表的 RSA 算法，由于其简单、易于理解，安全性高，广泛应用在密码领域。因此，高性能、低成本、安全性高的硬件实现是当前嵌入式领域研究的热点。 本文在对 RSA 模幂算法
基于Montgomery算法的高速、可配置 RSA密码IP核硬件设计系列(六)——模乘模块的设计实现方案
用心记录每天的学习，提升自己，虽然有的很基础但真的很重要！
02-27 1851
基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列（六）2.3 蒙哥马利模乘模块设计2.3.1 模乘模块功能 原创声明：本系列所有的博文都是本人参考相关的文献资料后，独立撰写，组织语言后，编写本系列博文，如需转载，请注明转载出处； 基于Montgomery算法的高速、可配置 RSA密码IP核硬件设计系列(六) 本次第六部分主要介绍相关项目的具体模块的设计方案，如模乘模块的设计方案； 2.3 蒙哥马利模乘模块设计 2.3.1 模乘模块功能 蒙哥马利模乘运算模块时整个RSA IP核的设计核心
基于FPGA的图像卷积运算（支持多通道，多分辨率）
yang_wei_jy的博客
01-06 596
`timescale 1 ps / 1 ps module tst_tb; reg clk ; reg rst_n ; initial begin clk = 0 ; rst_n = 0; #100 rst_n =1 ; end always #5 clk <= ~clk ; ///----------------------------...
【一】基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列
qq_31515205的博客
02-28 164
【一】基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列
蒙哥马利幂模a^b%n
神奇海螺的博客咯
09-07 523
Problem 1271 求A^B的最后三位数 【Description】 A^B的含义是“A的B次方” ，1<=A,B<=1000000000。请你编程计算A^B的最后3位数。 【Input】 输入有多个案例。每个案例占一行，每行两个数A、B。当A=0，B=0时表示结束。 【Ouput】 每行对应输出一个结果。 【Sample Input】 2 3 12 6 6789 10000 9...
大数取模之蒙哥马利幂模运算(a * b) % p = a % p * b % p % p
最新发布
qq_41577650的博客
12-05 1236
蒙哥马利幂模运算（Montgomery Modular Exponentiation）是一种用于计算大数的幂模运算的高效算法。该算法通过对中间结果进行转换，使得每次幂乘法运算的结果可以在模运算之前进行简化，从而减少模运算的次数，提高计算速度。蒙哥马利幂模运算是一种高效的幂模运算算法，通过对中间结果进行转换，减少模运算的次数，从而提高计算速度。这种算法在计算大数的幂模运算时特别有用，可以在需要求解大数幂模运算问题时使用。以上给出的Java代码实现了蒙哥马利幂模运算算法，并提供了示例供你参考和使用。
蒙哥马利算法求解大整数幂求模
专栏
03-31 8687
蒙哥马利大整数模幂算法   前几天写了一篇博客《25行代码实现完整的RSA算法》，是关于用Python代码实现一个完整的RSA算法的代码，整个代码中最核心、最浪费时间的代码部分就是关于求解大整数模幂算法这里。整个算法也叫“蒙哥马利幂模”算法。   首先简单介绍一下蒙哥马利相关的几个算法，具体详细介绍可以参考《蒙哥马利算法详解》。蒙哥马利算法并不是一个独立的算法，而是三个相互独立又相互联系的算法...
基于Montgomery算法的高速、可配置 RSA密码IP核硬件设计系列(七)——模乘内部各个模块的设计实现方案
用心记录每天的学习，提升自己，虽然有的很基础但真的很重要！
02-27 1618
基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列（七）2.3.3 蒙哥马利内部各模块的实现方案2.3.3.1 加法器设计方案2.3.3.2 压缩器(Compressor)设计方案2.3.3.3 Booth乘法器设计方案 原创声明：本系列所有的博文都是本人参考相关的文献资料后，独立撰写，组织语言后，编写本系列博文，如需转载，请注明转载出处； 基于Montgomery算法的高速、可配置 RSA密码IP核硬件设计系列(七) 本次第七部分主要介绍相关项目的具体模块的设计方案，如模乘内部各个模块
基于Montgomery算法的高速、可配置 RSA密码IP核硬件设计系列(五)——模幂模块（抵抗侧信道攻击）模块的设计实现方案
用心记录每天的学习，提升自己，虽然有的很基础但真的很重要！
02-27 1236
基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列（五）2.2 模幂模块设计(抵抗测信道攻击模块)2.2.1 模幂模块及内部模块的功能2.2.3 模幂各模块的实现方案2.2.3.1 随机伪操作与指数掩码(抵抗测信道攻击)的实现方案2.2.3.2 状态机控制的实现方案2.2.3.3 数据通路的实现方案2.2.3.4 FIFO块的实现方案 原创声明：本系列所有的博文都是本人参考相关的文献资料后，独立撰写，组织语言后，编写本系列博文，如需转载，请注明转载出处； 基于Montgomery算法的高
论文研究-Montgomery模乘算法的改进及其应用.pdf
09-06
Montgomery算法是目前最适合于通用处理器软件实现的大整数模乘算法。1996年，Koc总结了该算法的五种实现方法：SOS、CIOS、FIOS、FIPS和CIHS，并指出CIOS方法综合性能较优。首先深入分析了FIOS实现方法，并通过消除进位传递和减少循环控制等手段，提出了一种改进方法IFIOS。然后将该方法应用于模幂计算，给出了基于滑动窗口技术的Montgomery模幂算法。最后理论分析和实验结果表明，该改进将FIOS的执行速度提高了约54%，与目前常用的CIOS方法相比，亦有较大的优势。
蒙哥马利幂模算法（二分快速幂）
白白旧维的博客
07-15 1353
蒙哥马利幂模算法（二分快速幂） 用于加快幂次取模运算的速度。 形式为这种ab%c 可以等于 (ab1%c)*(ab2%c)%c，其中b=b1+b2；如果b1=b2就更简便一些，(ab/2%c)2%c，只要把数拆成平方的形式就可以使用幂次转二进制的简便运算了。即把x2的幂次转二进制为x10 比如求解某一个值xn%m：513%7 首先把n以二进制显示：13(10) = 1101(2) 。定义结果值 r，初始化为1。基值x：n值每次除以2则x就需要加倍。每轮判断n值最末尾位：如果为1，则就表示结果值 r 需
HDU 1420 蒙哥马利幂模算法
weixin_30371469的博客
03-21 210
Prepared for New Acmer http://acm.hdu.edu.cn/showproblem.php?pid=1420 蒙哥马利幂模思想： 在幂模运算中，通常是用幂模运算转换为乘模运算。有以下两个公式： 1）a*b%n=（a%n)*(b%n)%n 2）（a+b）%n=（a%n+b%n)%n 当我们计算D=C^15%N时，...
快速幂模－蒙哥马利－递推－HDU4506－HDU1211－HDU1575
CSDN
01-20 2286
小明系列故事——师兄帮帮忙 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 3699    Accepted Submission(s): 965 Problem Description 　　小明自从告别了ACM/ICPC
蒙哥马利基2的算法的Verilog 硬件实现（大数模乘）
用心记录每天的学习，提升自己，虽然有的很基础但真的很重要！
07-20 5165
`timescale 1ns / 1ps module montgomery #(parameter WIDTH =1024) ( input clk, input rstn, input start_flag, input [(WIDTH-1...
判断素数问题（费马小定理，蒙哥马利模幂）
Zunko的博客
04-02 788
题目描述 给定多个大于 1 的整数，判断是否为素数 输入 输入多行，每行是一个大于 1 的整数或字母 q 输出 对于每一行输入： 如果该行是正整数，那么输出一行，输出内容为 T 或 F，代表这个正整数是或不是素数； 如果该行是字母 q，则退出程序 样例输入 8888 123 29 q 样例输出 F F T 解法 对待判断数p，取几个素数a验证a^（p-1）与1模p同余，根据费马小定理若不同余，则p为合数，因此通过多取不同的素数进行检验能够极大概率保证准确率。 而同时使用蒙哥马
蒙哥马利幂模运算
immiao的专栏
04-20 2044
蒙哥马利幂模运算 简介 蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法，是RSA加密算法的核心之一。 特点及原理 蒙哥马利模乘的优点在于减少了取模的次数（在大数的条件下）以及简化了除法的复杂度（在2的k次幂的进制下除法仅需要进行左移操作）。模幂运算是RSA 的核心算法，最直接地决定了RSA 算法的性能。 针对快速模幂运算这一课题，西方现代数学家提出了大量的解决方案
蒙哥马利大数模乘与RSA加密算法简介
微微一电很蒟蒻
01-23 2168
今年复旦微电子电子设计比赛的题目是蒙哥马利大数模乘，在网上看了一圈蒙哥马利算法相关的博客，没有看到讲得比较通俗易懂的，干脆闲下来自己写一篇。 本文分为上中下三篇，内容如下： 上篇：蒙哥马利模乘的简介，RSA加密算法的简介，以及两者的关系。 中篇：蒙哥马利模乘的具体实现和优化，以及能否抵御几种常见的侧信道攻击。 下篇：蒙哥马利模乘的电路实现与验证，以及性能的分析。 ...
模板_快速幂+蒙哥马利快速幂模_二分思想_logn
喵 喵 喵~
04-25 459
一、积模分解公式 对于正整数X, Y, M， (X*Y)%M=((X%M)*(Y%M))%M 二、快速幂算法 如求2^7, 一般情况需要进行7次乘法运算，即1*2*2*2*2*2*2*2 可以将2*2结果保留下来: (2*2)*(2*2)*(2*2)*2=4*4*4*2 再把4*4保留下来（4*4）*（4*2） *************************************...
评论 2
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

摆渡沧桑

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值