非对称加密算法的研究与设计论文终稿

华北科技学院毕业论文

绍，着重介绍了公钥密码体制的基本知识：如二进制运算、整数除法、模运算、欧拉函数、费尔马小定理、欧几里德算法、概率算法、推荐的素性检验；算术基本定理、中国剩余定理、分治法基本思想。并分析RSA加解密过程及算法实现；针对RSA的攻击做简要分析，如因数分解攻击、选择密文攻击、对加密指数的攻击、对解密指数的攻击、明文攻击、对模的攻击、执行攻击；RSA加密算法的优缺点分析。根据理论基础设计RSA算法的程序，并在VC6.0软件平台下实现RSA算法的加密解密。

RSA算法是第一个既能用于数据加密也能用于数字签名的算法，算法的名字以发明者的名字命名。算法中使用的公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。先选择两个大素数p和q（2?p、q?216?65536），且p?q。计算：n=p*q然后随机选择加密密钥e，要求e和(p-1)*(q-1)互质。最后，利用Euclid算法计算解密密钥d,满足e*d=1(mod(p-1)*(q-1))其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。加密信息m时，首先把m分成等长数据块m1，m2，??mi，块长s，其中2^s<=n，s尽可能的大。对应的密文是：ci?miemodn—(a)；解密时作如下计算：mi?cidmodn—(b)。这就是RSA的加解密过程。

RSA可用于数字签名，用(a)式签名，(b)式验证。具体操作时考虑到安全性和m信息量较大等因素，一般是先作HASH运算。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。由于进行的都是大数计算,使得RSA最快的情况也比DES慢上100倍,无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。

关键词：RSA；RSA算法；加密；解密；非对称密钥；密码学；公钥；私钥。

第5页共62页

非对称密码学加密算法的研究与设计――RSA算法的程序设计

Introduction

Cryptography is an important information security technologies for protection of state secrets and an important tool for decision-making is also important to protect personal information and other information important way. Information can effectively protect the confidentiality, integrity and differentiation. Cryptography research involves many technical learning, including how to data encryption and how to send encrypted data, how to decrypt the encrypted data, so that the legitimate needs of those who have their own data to the data

Cryptography is the preparation of the password and decrypt the password of the technical sciences. Cryptography usually consists of two branches of the unity of opposites: Cryptography and cryptanalysis. Cryptography and cryptanalysis complementary study were in the unity of cryptography. In addition to including modern cryptography and cryptanalysis Cryptography study two main subjects, but also includes a new branch of production - the password key learning. It is based password system, the core part of the key as the study subjects. Key management is a point of order, which includes key generation, distribution, storage, protection, destruction and other links. Constitute the three branches of the major modern scientific system of cryptography.

Public key cryptosystem is the most important of modern cryptography invention and progress. Send and receive information of the real identity verification, on the issue / receive information after the fact of non-repudiation and data integrity protection is the subject of modern cryptography, on the other hand. The main features of public key cryptography algorithm is the encryption and decryption use different keys (public key and private key), and the encryption key can open, but only conservative in the confidential decryption key cryptographic algorithm. Public key and private key are a pair, if the public key used to encrypt the data, only using the corresponding private key can decrypt; if the private key used to encrypt the data, then only the corresponding public key can be used decryption. In this encryption algorithm, encryption key from the public can not derive the secret decryption key, can not ciphertext from the encryption key and the corresponding plaintext recovery. The most influential public key cryptography algorithm is RSA, it can resist all the passwords so far known attacks. In the public key system, the encryption key is different from the decryption key. It will be made public encryption key, anyone can use; the decryption key only to decrypt themselves know. So far all the public key system, RSA system is the best known and most widely used one.

第6页共62页

华北科技学院毕业论文

Asymmetric cryptography features: intensity of complex algorithms, security depends on the algorithm and key, but because of its computational complexity, and makes encryption and decryption speed is not fast symmetric encryption and decryption. Symmetric encryption system is only one key, and non-public, if you want to have to let each other know the decryption key. Therefore, to ensure their safety is to ensure security of the keys rather than symmetric key system, there are two keys, one of which is open, so that you can transfer without the other party as symmetric encryption key as a. This security on large lot.

This research project mainly in the non-symmetric encryption algorithm encryption algorithm code RSA. On cryptography is briefly introduced, highlighting the basics of public key cryptography: as binary operations, integer division, modular arithmetic, Euler function, Fermat's little theorem, Euclidean algorithm, probabilistic algorithms, recommendation primality test; the fundamental theorem of arithmetic, Chinese Remainder Theorem, divide and conquer the basic idea. And analyze the RSA encryption and decryption process and the algorithm; for a brief analysis of RSA attack, such as factoring attack, chosen ciphertext attack on the encryption exponent attack, the attack on the decryption exponent, plaintext attack, on the mode of attack, an attack ; RSA encryption algorithm analyzes the advantages and disadvantages. RSA algorithm is based on theoretical foundation design procedures and software platform to achieve in VC6.0 RSA algorithm encryption and decryption.

RSA algorithm is the first not only for data encryption can be used for digital signature algorithm, the algorithm's name to the inventor's name. Algorithm using the public key and private key are two large prime numbers (greater than 100 decimal places) of the function. It is assumed that key and ciphertext from a plaintext of the difficulty to infer equivalent decomposition of the product of two large prime numbers. First select two large prime numbers p and q (), and. Calculation: n = p * q and then randomly selected encryption key e, e and requirements (p-1) * (q-1) are coprime. Finally, Euclid algorithm decryption key d, to satisfy e * d = 1 (mod (p-1) * (q-1)) where n and d have coprime. E and n is the number of public key, d is the private key. Two primes p and q are no longer needed, it should be discarded, do not let anyone know. Encrypted message m, first of all the m divided into equal length blocks of data m1, m2, ... ... mi, block size s, where 2 ^ s <= n, s as large as possible. Corresponding ciphertext is: - (a); decryption calculated as follows: - (b). This is the RSA encryption and decryption process.

第7页共62页

非对称密码学加密算法的研究与设计――RSA算法的程序设计

RSA can be used for digital signatures, using (a) type signature, (b) authentication. Specific operation, take into account the large amount of information security and m factors, generally the first operations for HASH. RSA's security depends on the integer factorization, but is equivalent to factoring has not been proved theoretically. Currently, RSA algorithm for some variants have been proven equivalent to factoring. In any case, decomposition of n is the most obvious attack method. Now, more than 140 people have been able to decompose a large prime number decimal places. Therefore, the modulus n must be selected larger, because of the specific application conditions. As a result of large numbers are calculated, making the fastest RSA situation 100 times slower than DES, either software or hardware. RSA has been the defect rate. Generally used only for a small amount of data encryption.

Keywords: RSA; RSA algorithm; encryption; decryption; non-symmetric key; cryptography; public key; private key.

第8页共62页