RSA Modular Exponentiation Implementation
1. RSA algorithm
The keys for the RSA algorithm are generated the following way:
1. Choose two distinct prime numbers and .
For security purposes, the integers p and q should be chosen at random, and should be similar
in magnitude but differ in length by a few digits to make factoring harder. Prime integers can be
efficiently found using a primality test (https://en.wikipedia.org/wiki/Primality_test).
2. Compute .
is used as the modulus for both the public and private keys. Its length, usually expressed in
bits, is the key length.
3. Compute , where is Carmichael's totient function
(https://en.wikipedia.org/wiki/Carmichael%27s_totient_function). This value is kept private.
4. Choose an integer such that and ; i.e., and are coprime.
5. Determine as ; i.e., is the modular multiplicative inverse of
.
This is more clearly stated as: solve for given .
having a short bit-length and small Hamming weight
(https://en.wikipedia.org/wiki/Hamming_weight) results in more efficient encryption – most
commonly . However, much smaller values of (such as 3) have been
shown to be less secure in some settings.
is released as the public key exponent.
is kept as the private key exponent.
1.1. Encryption
For messages to be encrypted is first transfer into an integer by using padding. such that
by using an agreed-upon reversible protocol known as a padding scheme. Then computes the ciphertext ,
using public key , corresponding to
1.2. Decryption
To recover from by using her private key exponent d by computing
2. Calculate
2.1. Right-to-left binary method
First, it is required that the exponent e be converted to binary notation. That is, e can be written as:
p q
n
=
pq
n
λ
(
n
) =
lcm
(
λ
(
p
),
λ
(
q
)) =
lcm
(
p
− 1,
q
− 1)
λ
e
1 <
e
<
λ
(
n
)
gcd
(
e
,
λ
(
n
)) = 1
e
λ
(
n
)
d
d
≡ (mod
λ
(
n
))
e
−1
d
e
(mod
λ
(
n
))
d
d
⋅
e
≡ 1 (mod
λ
(
n
))
e
e
= + 1 = 65,537
2
16
e
e
d
M
m
0 ≤
m
<
n
c
e
c
≡ (mod
n
)
m
e
m c
≡ ( ≡
m
(mod
n
)
c
d
m
e
)
d
c
≡ (mod
n
)
m
e
e
=
∑
n
−1
i
=0
a
i
2
i
下载后可阅读完整内容，剩余4页未读，立即下载
_没有感情的程序员
- 粉丝: 0
- 资源: 7
我的内容管理
展开
最新资源
- 多传感器数据融合手册：国外原版技术指南
- MyEclipse快捷键大全，提升编程效率
- 从零开始的编程学习：Linux汇编语言入门
- EJB3.0实例教程：从入门到精通
- 深入理解jQuery源码：解析与分析
- MMC-1电机控制ASSP芯片用户手册
- HS1101相对湿度传感器技术规格与应用
- Shell基础入门：权限管理与常用命令详解
- 2003年全国大学生电子设计竞赛：电压控制LC振荡器与宽带放大器
- Android手机用户代理(User Agent)详解与示例
- Java代码规范：提升软件质量和团队协作的关键
- 浙江电信移动业务接入与ISAG接口实战指南
- 电子密码锁设计：安全便捷的新型锁具
- NavTech SDAL格式规范1.7版：车辆导航数据标准
- Surfer8中文入门手册：绘制等高线与克服语言障碍
- 排序算法全解析：冒泡、选择、插入、Shell、快速排序
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
