个性化阅读
专注于IT技术分析

如何解决RSA算法问题?

RSA算法这是一种非对称密码算法, 这意味着在通信时应涉及两个密钥, 即公钥和私钥。解决RSA算法问题的步骤很简单。

示例1:

步骤1:选择两个质数

p

q

让我们来

p = 3

q = 11

步骤2:计算的值

ñ

\ phi

给出为

and

在这个例子中

n = 3 \乘11 = 33
\ phi =(3-1)\ times(11-1)= 2 \ times 10 = 20

步骤3:找出的值

(公钥)

选择

, 这样

应该是互质的。互素意味着它不应该乘以

\ phi

而且不除以

\ phi

影响因素

\ phi

是,

20 = 5次4 = 5次2次

so

不应乘以

5

2

并且不应除以20。

因此, 素数是3、7、11、17、19…, 因为选择了3和11

如7

因此,

e = 7

步骤4:计算的值

d

(私钥)

条件为

gcd(\ phi,e)= \ phi x + ey = 1

y是

d

.

计算的值

d

,

形成一个包含四列的表, 即a, b, d和k。

初始化a = 1, b = 0, d =

\ phi

, k = –第一行。

初始化a = 0, b = 1, d =

,

k = \ frac {\ phi} {e}

在第二排。

在下一行中, 应用以下公式查找下一个a, b, d和k的值, 其值如下所示:

a_ {i} = a_ {i-2}-(a_ {i-1} \ k_ {i-1})
b_ {i} = b_ {i-2}-(b_ {i-1} \次k_ {i-1})
d_ {i} = d_ {i-2}-(d_ {i-1} \次k_ {i-1})
k_ {i} = \ frac {d_ {i-1}} {d_ {i}}

立刻,

d = 1

, 请停止该过程并检查以下情况

if 
    
if

对于给定的示例, 该表将为

一种 b d ķ
1 0 20
0 1 7 2
1 -2 6 1
-1 3 1

如上表

d = 1

, 请停止该过程并检查为

b
\因此b = 3

验证

b

是正确的, 上述条件应满足, 即

gcd(\ phi,e)= \ phi x + ey =(20 x -1)+(7 x 3)= 1

。因此

d

是正确的。

步骤5:进行加密和解密

加密方式为

c = t ^ {e} \ mod n

解密为

t = c ^ {d} \ mod n

对于给定的示例, 假设

t = 2

, 所以

加密是

c = 2 ^ {7} \ mod 33 = 29

解密为

t = 29 ^ {3} \ mod 33 = 2

因此, 在最后,

p = 3

,

q = 11

,

\ phi = 20

,

n = 33

,

e = 7

d = 3

示例2:

GATE CS-2017(Set 1)

在RSA密码系统中, 特定的A使用两个质数p = 13和q = 17生成她的公钥和私钥。如果A的公钥是35。那么A的私钥是?

p = 13

q = 17

计算

n = 13 \乘以17 = 221

\ phi =(13-1)\倍(17-1)= 12 \倍16 = 192
e = 35

(公钥)

计算

d

(私钥)

a b d k
1 0 192
0 1 35 5
1 -5 17 2
-2 11 1
\因此d = 11

(私钥)


赞(0) 打赏
未经允许不得转载:srcmini » 如何解决RSA算法问题?
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏