加密：RSA算法 [英] encryption : RSA algorithm

问题描述

我实现RSA算法进行加密和解密，如下给出：

I am implementing the RSA algorithm for encryption and decryption as given here:

http://www.di-mgt.com.au/rsa_alg.html

但不明白的密钥生成随机素数生成的一部分。
所以我采取两个素数从用户输入。我曾与生成电子也困难。所以我把它常数（E = 17）

But could not understand the random prime number generation part in key generation. So I am taking two prime numbers as inputs from user. I had difficulties with generating the e also. so I made it constant (e= 17)

一些素数在输入linux下的gcc正常工作（即编码和解码正确），但不DEVCPP在windows下。 （如53,61）

Some prime number inputs working properly ( i.e encoding and decoding properly) in gcc under linux but not in devcpp under windows. (e.g 53,61)

下面是密钥生成code：

Here is the key generation code:

/* Generates private and public keys and saves into two separate files */
void keygen()
{
    int p,q,phi,d,e,n,s;

    printf("\n Enter two prime numbers: ");
    scanf("%d%d",&p,&q);

    n = p*q;
    phi=(p-1)*(q-1);

    e=17;

    // selec d such that d*e = 1+ k*phi for some integer k.
    d = 0;
    do
    {
        d++;
        s = (d*e)%phi;
    }while(s!=1);

    printf("\n public key: { e=%d n=%d }",e,n);
    printf("\n private key: { d=%d n=%d }\n",d,n);

}

需要帮助和建议的素数，e世代。

Need help and suggestions in the prime number and e generation.

推荐答案

所以你已经知道* D + E必须一致，以1 MOD岛（N）

so you already know that e * d needs to be congruent to 1 mod phi(n)

因为你知道岛（n）的一个元组（E，D）可以通过使用扩展欧几里德算法（EEA）计算：

since you know phi(n) a tuple (e,d) can be calculated by using the extended euclidean algorithm (EEA):

选择为电子商务的一个整数（通常是一个小整数，这将是公开指数，加密将与小指数更快）小于岛（n）和大于2（...我觉得呢？）

choose an integer for e (usually a small integer; this will be the public exponent, encryption will be faster with smaller exponents) that is less than phi(n) and greater than 2 (?... i think)

当你为电子商务的候选人，计算e和岛（N）...的最大公约数（GCD）应为1 ...如果不是，选择e和重复一个新的​​候选（因为会没有模逆，换句话说，没有私有指数d存在这个电子和phi（N））

when you have a candidate for e, calculate the greatest common divisor (gcd) of e and phi(n) ... should be 1 ... if not, choose a new candidate for e and repeat (since there would be no modular inverse, in other words no private exponent d exists for this e and phi(n))

你知道后GCD（E，披（N））== 1就可以计算出使用EEA D（或快捷方式，计算EEA直接，因为它也将提供GCD ......如果这不是1，选择为电子新值）

after you know that gcd(e,phi(n))==1 you can calculate d using the EEA (or as a shortcut, calculate EEA directly since it will also provide the GCD ... if that's not 1, choose a new value for e)

EEA（快速和肮脏的计算模逆）：

EEA (quick and dirty for calculating modular inverse):

想象与3列的表格：

可以说那些列被命名为：B，Q和T

lets say those columns are named: b, q and t

使表的线条看起来像：

B0，Q0，T0结果
B1，Q1，T1结果
...结果
（等）

b0, q0, t0
b1, q1, t1
...
(and so on)

的前2行最初将填充。
对于所有其它行有可施加到previous两行，这将导致对下一行

the first 2 rows will be initially filled. for all other rows there is an itterative rule that can be applied to the previous two rows that will result in the values for the next row

前2行是：

岛（N），NO_VALUE，0结果
即，地板（PHI（N）/ E），1

phi(n), NO_VALUE, 0
e, floor(phi(n)/e), 1

在itterative规则以创建下一行是：（其中[]是一个索引操作符用于选择行）

the itterative rule to create the next row is: (where [] is an index operator for selecting the row)

B〔Ⅰ〕= B [Ⅰ-2]模B〔I-1〕搜索
Q [i] = B [I-1] / B [I]（整数除法，分数不...）结果
T [I] = T [I-2] - （Q [I-1] * T [I-1]）

b[i] = b[i-2] mod b[i-1]
q[i] = b[i-1] / b[i] (integer division, no fractions ... )
t[i] = t[i-2] - ( q[i-1] * t[i-1] )

您可以中止该计划当b [I]变为0或1 ...你真的不需要•对于最后一排...

you can abort the scheme when b[i] becomes 0 or 1 ... you don't really need q for the last row ...

所以若B [i]为0，B [I-1]不能1，因为你应该中止，当你计算出的B〔I-1]如果这是1 ...

so if b[i] is 0, b[i-1] can not be 1 since you should have aborted when you calculated b[i-1] if that were 1 ...

如果你达到B〔I] == 0，B [I-1]是你的GCD ...因为它不是1你需要为电子商务的新值

if you reach b[i]==0, b[i-1] is your gcd ... since it is not 1 you need a new value for e

如果B〔Ⅰ〕== 1的最大公约数为1，并且有一个逆...那是叔[I]（如果t为负，添加披（n））的

if b[i]==1 your gcd is 1, and there is an inverse ... and that is t[i] (if t is negative, add phi(n))

例如用实际值：

假设岛（n）是120
比方说，我们选择23为电子候选人

let's say phi(n) is 120 let's say we choose 23 as a candidate for e

我们的表看起来像：

b     q     t
120   –     0
23    5     1
5     4     -5
3     1     21
2     1     -26
1     2     47

最后计算b为1，因此=> GCD（23120）== 1（证明：逆存在）结果
最后计算t为47 => 23 * 47 120 MOD == 1（t为倒数）

the last calculated b is 1 so => gcd(23,120) == 1 (proof: the inverse exists)
the last calculated t is 47 => 23*47 mod 120 == 1 (t is the inverse)

这篇关于加密：RSA算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！