Con*_*ler 6 c++ encryption cryptography
我目前正在用C++ for Unix编写自己的ASE/RSA加密程序.我已经阅读了大约一个星期的文献,我已经开始围绕这一切,但我仍然有一些紧迫的问题:
1)根据我的理解,最基本形式的RSA密钥是所使用的两个素数(R)和指数的乘积的组合.对我来说很明显,以明文形式存储密钥会破坏加密任何东西的目的.因此,我可以以什么形式存储生成的公钥和私钥？询问用户密码并使用ASCII表对密钥的各个数字进行"简单"移位/替换？或者是否有其他标准我还没有遇到过？此外,当生成密钥时,R和相应的指数是否顺序存储？即## primeproduct #### exponent ##？在这种情况下,解密算法如何将密钥解析为两个单独的值？
2)鉴于我决定使用65537作为所有加密的公共指数,我将如何以编程方式生成私有指数？我得到了方程P*Q = 1mod(M),其中P和Q以及指数和M是Euler's Totient函数的结果.这只是产生随机数并测试它们对公众指数的相对素数直到你付出肮脏的问题吗？我知道你不能简单地从1开始增加直到找到这样的数字,因为任何人都可以简单地做同样的事情并自己获得你的私人指数.
3)当生成字符等价集时,我理解集合中使用的数字不能小于并且相对于P*Q的素数.同样,这是测试数字相对于P*Q的素数的问题.测试相对素数的速度是否与您正在使用的数字的大小无关？或者是必要的特殊算法？
提前感谢任何花时间阅读和回答的人,欢呼!
有一些标准格式用于存储/交换RSA密钥,例如RFC 3447.无论好坏,大多数(许多人,无论如何)使用ASN.1编码,这增加了比大多数人喜欢的复杂性,这本身就是全部.一些使用Base64编码,这更容易实现.
至于构成关键词的是什么:在最基本的形式中,你是正确的; 公钥包括模数(通常称为n)和指数(通常称为e).
要计算密钥对,可以从两个大的素数开始,通常称为p和q.您将模数计算n为p * q.您还可以计算一个(通常称为r)数字(p-1) * (q-1).
e然后是或多或少随机选择的数字,相对于r.警告:你不想e真的很小 - 尽管log(e)> = log(n)/ 4是最低限度的.
然后,您d(私有解密密钥)计算为满足关系的数字:
d * e = 1 (mod r)
您通常使用Euclid算法计算此值,但还有其他选项(见下文).同样,你也不想d变得非常小,所以如果它真的很小,你可能想要尝试另一个值e,并计算一个新d的匹配.
还有另一种计算你e和你的方法d.你可以从找到一个与1 mod r一致的数字K开始,然后考虑它.将素数因子放在一起得到大小相等的两个因子,并将它们用作e和d.
至于计算你的攻击者d:你需要r计算这个,知道r取决于知道p和q.这正是为什么/在哪里/如何分解破坏RSA.如果您因素n,那么你知道p和q.从他们那里,你可以找到r,并从r你可以计算出d与已知的匹配e.
所以,让我们通过数学来创建一个密钥对.我们要使用的素数多过小是有效的,但应足以证明所涉及的想法.
所以让我们从选择ap和q开始(当然,两者都需要是素数):
p = 9999991
q = 11999989
从那些我们计算n和r:
n = 119999782000099
r = 119999760000120
接下来我们需要选择e或者计算K,然后将其计算得到e和d.目前,我们将继续你的建议e = 65537(因为65537是素数,唯一的可能性,而r不是相对质数将是如果r是65537的精确倍数,我们可以验证不是这样的情况容易).
从那以后,我们需要计算我们的d.我们可以相当容易地(尽管不一定非常快)使用Euclid算法的"扩展"版本(如你所提到的)Euler's Totient,Gauss'方法或任何其他方法.
目前,我将使用高斯方法计算它:
template <class num>
num gcd(num a, num b) {
num r;
while (b > 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
template <class num>
num find_inverse(num a, num p) {
num g, z;
if (gcd(a, p) > 1) return 0;
z = 1;
while (a > 1) {
z += p;
if ((g=gcd(a, z))> 1) {
a /= g;
z /= g;
}
}
return z;
}
我们得到的结果是:
d = 38110914516113
然后我们可以将它们插入到RSA的实现中,并使用它们来加密和解密消息.
所以,让我们加密"非常秘密的消息!".使用e和n上面给出,即要进行加密:
74603288122996
49544151279887
83011912841578
96347106356362
20256165166509
66272049143842
49544151279887
22863535059597
83011912841578
49544151279887
96446347654908
20256165166509
87232607087245
49544151279887
68304272579690
68304272579690
87665372487589
26633960965444
49544151279887
15733234551614
并且,使用d上面给出的,解密回原始.执行加密/解密的代码(使用硬编码密钥和模数)如下所示:
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <functional>
typedef unsigned long long num;
const num e_key = 65537;
const num d_key = 38110914516113;
const num n = 119999782000099;
template <class T>
T mul_mod(T a, T b, T m) {
if (m == 0) return a * b;
T r = T();
while (a > 0) {
if (a & 1)
if ((r += b) > m) r %= m;
a >>= 1;
if ((b <<= 1) > m) b %= m;
}
return r;
}
template <class T>
T pow_mod(T a, T n, T m) {
T r = 1;
while (n > 0) {
if (n & 1)
r = mul_mod(r, a, m);
a = mul_mod(a, a, m);
n >>= 1;
}
return r;
}
int main() {
std::string msg = "Very Secret Message!";
std::vector<num> encrypted;
std::cout << "Original message: " << msg << '\n';
std::transform(msg.begin(), msg.end(),
std::back_inserter(encrypted),
[&](num val) { return pow_mod(val, e_key, n); });
std::cout << "Encrypted message:\n";
std::copy(encrypted.begin(), encrypted.end(), std::ostream_iterator<num>(std::cout, "\n"));
std::cout << "\n";
std::cout << "Decrypted message: ";
std::transform(encrypted.begin(), encrypted.end(),
std::ostream_iterator<char>(std::cout, ""),
[](num val) { return pow_mod(val, d_key, n); });
std::cout << "\n";
}
为了获得安全的希望,你需要使用更大的模数 - 至少数百比特(对于偏执狂来说可能是一千或更多).您可以使用普通的任意精度整数库或专门为手头任务编写的例程来实现.RSA本质上相当慢,因此大多数实现一度使用具有大量毛发优化的代码来完成工作.如今,硬件足够快,你可以很容易地使用一个相当平均的大整数库(特别是在实际使用中,你只想使用RSA加密/解密密钥用于对称算法,而不是加密原始数据).