素数原理的加密算法

㈠ 利用质数如何加密

非对称加密。1976年，美国学者Dime和Henman为解决信息公开传送和密钥管理问题，提出一种新的密钥交换协议，允许在不安全的媒体上的通讯双方交换信息，安全地达成一致的密钥，这就是“公开密钥系统”。 相对于“对称加密算法”这种方法也叫做“非对称加密算法”。

与对称加密算法不同，非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。非对称加密与对称加密相比，其安全性更好：对称加密的通信双方使用相同的秘钥，如果一方的秘钥遭泄露，那么整个通信就会被破解。而非对称加密使用一对秘钥，一个用来加密，一个用来解密，而且公钥是公开的，秘钥是自己保存的，不需要像对称加密那样在通信之前要先同步秘钥。非对称加密的缺点是加密和解密花费时间长、速度慢，只适合对少量数据进行加密。

在非对称加密中使用的主要算法有：RSA、Elgamal、背包算法、Rabin、D-H、ECC（椭圆曲线加密算法）等。不同算法的实现机制不同，可参考对应算法的详细资料。

甲乙之间使用非对称加密的方式完成了重要信息的安全传输。

1、乙方生成一对密钥（公钥和私钥）并将公钥向其它方公开。

2、得到该公钥的甲方使用该密钥对机密信息进行加密后再发送给乙方。

3、乙方再用自己保存的另一把专用密钥（私钥）对加密后的信息进行解密。乙方只能用其专用密钥（私钥）解密由对应的公钥加密后的信息。

在传输过程中，即使攻击者截获了传输的密文，并得到了乙的公钥，也无法破解密文，因为只有乙的私钥才能解密密文。同样，如果乙要回复加密信息给甲，那么需要甲先公布甲的公钥给乙用于加密，甲自己保存甲的私钥用于解密。

㈡ 密码学（三）RSA算法以及一些因数分解法

RSA算法详解：基于公钥加密系统

RSA算法，以三位科学家的姓氏命名，构建了现代密码学中的核心部分。这个广泛使用的密码体制基于两个关键步骤：素数选择与加密解密过程。首先，Alice和Bob需选择两个素数p和q，再选定一个数n，满足n=p*q。他们公开共享公钥(e)，以及n，其中e与(p-1)*(q-1)互质。

Alice要加密信息m，会将m进行如下操作：m^e mod n。将得到的密文c发送给Bob。Bob接收到密文后，通过计算d（模p-1和模q-1的逆元）进行解密，即c^d mod n，得到原始消息m。

RSA的安全性基于大数分解的难度，但在特殊情况下，如 Woman in the middle attack，如果Eva掌握了加密规则，可以通过精心设计的假密文攻击。她不需要直接分解n，只需对密文进行简单的操作，就能轻易获取信息，破坏系统。

对于素数分解，虽然一般情况下的复杂度是难以克服的，但在某些特定条件下，如Miller-Robin素数判别法，能快速识别非素数，尽管存在Carmichael Number这类特殊情况。Miller-Robin定理基于费马小定理，对奇素数和奇合数的特性提供判断依据。

Pollard's p-1分解法和平方差分解法，针对特定情况如两个素数乘积，提供了分解方法。Pollard's p-1法通过寻找合适倍数，利用费马小定理寻找因数，而平方差分解则利用两个数的平方差寻找因子，是目前最快的分解法之一。

最后，数论中的黎曼猜想和素数分布理论为这些分解法提供了理论支持，包括黎曼ζ函数和数域筛法。数域筛法，尽管复杂，但当处理大型数值时，它是最快的素因数分解技术。平方筛法则是其中一种简化版本，通过筛选和计算，寻找B光滑数，进一步提高分解效率。

㈢ 质数的定义是什么 大质数加密的原理是什么

质数的定义：
质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数。
大质数加密的原理：
1、让计算机随机生成两个大质数p和q，得出乘积n；
2、利用p和q有条件的生成加密密钥e；
3、通过一系列计算，得到与n互为质数的解密密钥d，置于操作系统才知道的地方；
4、操作系统将n和e共同作为公匙对外发布，将私匙d秘密保存,把初始质数p和q秘密丢弃。
国际数学和密码学界已证明，企图利用公匙和密文推断出明文，或者企图利用公匙推断出私匙的难度等同于分解两个巨大质数的积，这就是Eve不可能对Alice的密文解密以及公匙可以在网上公布的原因。
至于"巨大质数"要多大才能保证安全的问题不用担心，利用当前可预测的计算能力，在十进制下，分解两个250位质数的积要用数十万年的时间；并且质数用尽或两台计算机偶然使用相同质数的概率小到可以被忽略。

㈣ 一个RSA算法的加密运算，需要完整的演算过程。

RSA算法非常简单，概述如下：
找两素数p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一个数e,要求满足e<t并且e与t互素（就是最大公因数为1）
取d*e%t==1
这样最终得到三个数：
n
d
e
设消息为数M
(M
<n)
设c=(M**d)%n就得到了加密后的消息c
设m=(c**e)%n则
m
==
M，从而完成对c的解密。
注：**表示次方,上面两式中的d和e可以互换。
在对称加密中：
n
d两个数构成公钥，可以告诉别人；
n
e两个数构成私钥，e自己保留，不让任何人知道。
给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。
别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。
rsa的安全性在于对于一个大数n，没有有效的方法能够将其分解
从而在已知n
d的情况下无法获得e；同样在已知n
e的情况下无法
求得d。
rsa简洁幽雅，但计算速度比较慢，通常加密中并不是直接使用rsa
来对所有的信息进行加密，
最常见的情况是随机产生一个对称加密的密钥，然后使用对称加密算法对信息加密，之后用
RSA对刚才的加密密钥进行加密。
最后需要说明的是，当前小于1024位的N已经被证明是不安全的
自己使用中不要使用小于1024位的RSA，最好使用2048位的。