留此记录或供同好参考，中英混合，有些乱勿怪。
RSA算法:RSA算法是基于大数难于分解的原理。不但可以用于认证，也可以用于密钥传输，例子可以参考RSAUtil.java文件。那么用户A和B如何利用RSA算法来传输密钥呢？
1：A产生一个密钥K，用B的公钥加密K，然后将得到的密文发送给B。
2：B用自己的私钥解密收到的密钥，就可以得到密钥。
DH算法:DH算法的出现就是用来进行密钥传输的。DH算法是基于离散对数实现的。DH算法的基本工作原理是：通信双方公开或半公开交换一些准备用来生成密钥的"材料数据"，在彼此交换过密钥生成"材料"后，两端可以各自生成出完全一样的共享密钥。在任何时候，双方都绝不交换真正的密钥。通信双方交换的密钥生成"材料"，长度不等，"材料"长度越长，所生成的密钥强度也就越高，密钥破译就越困难。除进行密钥交换外，IPSec还使用DH算法生成所有其他加密密钥。
在通信前，用户A和B双方约定2个大整数n和g,其中1<g<n，这两个整数可以公开
1) A随机产生一个大整数a，然后计算Ka=ga mod n（a需要保密）
2) B随机产生一个大整数b，然后计算Kb=gb mod n（b需要保密）
3) A把Ka发送给B,B把Kb发送给A
4) A计算K=Kba mod n
5) B计算K=Kab mod n
由于Kba mod n= （gb mod n）a mod n= （ga mod n）b mod n，因此可以保证双方得到的K是相同的，K即是共享的密钥。可以参考JCE文档中的DH 3 party的例子。
实际的一个用DH算法传递DES私钥的JAVA例子参看“JAVA上加密算法的实现用例”一文中的末一个例子，过程如下：假设A和B通信（JCE中只支持DH算法作为传递私钥的算法）
g 8 n 9
a 7 decSide
b 5 encSide
Ka=(g * a) % n= (8 * 7) % 9 pub = 2
Kb=(g * b) % n= (8 * 5) % 9 pri = 4
kaa = a % n = 7 % 9 = 7
kbb = b % n = 5 % 9 = 5
K, = kbb * a % n = (b % n) * a % n = 8
K, = kaa * b % n = (a % n) * b % n = 8
K = (Kb * a) % n = ((g * b) % n) * a % n =1
K = (Ka * b) % n = ((g * a) % n) * b % n =1
num: 10
K = 1, 2 * 5 % 9 = 1
encNum = 11
encSide: Ka=2, b=5, n=9
decSide: Kb=4, a=7, n=9
K=4*7%9=1
decNum=10
((g % n) * (b % n)) % n
((g % n) * (a % n)) % n
Pub100 * 51 % n
Pri102 * 50 % n
取模运算
对于整型数a，b来说，取模运算或者求余运算的方法都是：
1.求 整数商： c = a/b;
2.计算模或者余数： r = a - c*b.
求模运算和求余运算在第一步不同: 取余运算在取c的值时，向0 方向舍入(fix()函数)；而取模运算在计算c的值时，向负无穷方向舍入(floor()函数)。
例如：计算-7 Mod 4
那么：a = -7；b = 4；
第一步：求整数商c，如进行求模运算c = -2（向负无穷方向舍入），求余c = -1（向0方向舍入）；
第二步：计算模和余数的公式相同，但因c的值不同，求模时r = 1，求余时r = -3。
归纳：当a和b符号一致时，求模运算和求余运算所得的c的值一致，因此结果一致。
当符号不一致时，结果不一样。求模运算结果的符号和b一致，求余运算结果的符号和a一致。比如上式：-7取模4=1 -7取余4=-3
基本性质
（1）若p|(a-b)，则a≡b (% p) 即 a%p = b % p。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7) // | 表示整除
（2）(a % p)=(b % p)意味a≡b (% p)
（3）对称性：a≡b (% p)等价于b≡a (% p)
（4）传递性：若a≡b (% p)且b≡c (% p) ，则a≡c (% p)
运算规则
模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
ab % p = ((a % p)b) % p （4）
结合率：
((a+b) % p + c) % p = (a + (b+c) % p) % p （5）
((a*b) % p * c)% p = (a * (b*c) % p) % p （6）
交换率： (a + b) % p = (b+a) % p （7）
(a * b) % p = (b * a) % p （8）
分配率： ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）
重要定理
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）
若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（11）
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)， (a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）
若a≡b (% p)，则对于任意的c，都有ac≡ bc (%p)； （13）
问题: 扩展欧几里德算法求解线性同余方程
对于不完全为 0 的非负整数 a，b，gcd(a，b)表示 a，b 的最大公约数。那么存在唯一的整
数 x，y 使得 gcd(a，b)=ax+by。
一、递归
设 a>b。
1，显然当 b=0，gcd(a，b)=a。此时 x=1，y=0;
2，ab<>0 时
设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得:x1=y2; y1=x2-(a/b)*y2;
这样我们就得到了求解 x1,y1 的方法:x1，y1 的值基于 x2，y2.
上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以
The key to making reverse-engineering so expensive is using power-of. Square root is not so hard, power of 3 means you need a cubed root, but power of 34,051,489 is pretty hard. There are other mathematical operations that are difficult to reverse-engineer. There are also multiple ways to create an Asymmetric Algorithm, but this answer focuses on RSA. The oldest and most common.
RSA Algorithm (based on the Java Code)
The the below calculations should be done with arbitrary precision integers. (Such as BigInt or BigInteger)
Generating the keys:
Constant key length is l.
Usually constant e_start can =3 for simplicity. However, 0x10001 is more common, at any rate, a prime number is best (for key-generation performance reasons and probably other reasons).
p and q are the randomly generated positive prime numbers, that require up to l bits for storage. (To keep these positive, the first bit will always be 0)
n = p*q This is used for both the encryption and decryption.
e starts off as e_start. This will eventually be the part of the encryption key.
m = (p-1)*(q-1) is used to convert e to d, which will be used for decryption.
while(gcd(e,m)>1){e+=2} This is necessary for the next step to work.
d=modInverse(e,m) This performs a standard arithmatic operation. Probably not worth examining much, especially if your programming language has this built in
To encrypt or decrypt, first convert your bytes to a single arbitrary precision integer.
Encryption: encrypted=(plain^e)%n
Note: If plain>=n, you must split plain into two or more smaller values and encrypt them separately.
Decryption: plain=(encrypted^d)%n
Asymmetric encryption is typically less efficient than Symmetric encryption. Sometimes Asymmetric encryption is used only for key exchange.
The elementary working of Public Key Cryptography is best explained with an example. The working below covers the making of simple keys and the encryption and decryption of a sample of plain text. By necessity, the example is greatly simplified.
Basic Public Key Summary[edit]
Public key encryption is used for internet secure links, such as when a browser opens a bank site or a site used with credit cards. Such addresses are prefixed by https as opposed to just http. RSA-OpenSSL is such an encryption system. An example of this secure site marking can be seen on the address of this page; this Wikibooks page (when the user is logged in) shows the https prefix or some alternative browser-specific marking that indicates that it is considered secure.
Each site has an encryption key and a decryption key of its own, termed the public and private keys respectively. These are essentially very large numbers. These keys are always different, giving rise to the term asymmetrical encryption. In fact whenever we say key we mean a pair of numbers comprising the key; a key number to use in the raising of powers and another number that is the modulus of the arithmetic to be used for the work. For those unfamiliar with modular arithmetic, refer to the Wikibooks page High School Mathematics Extensions/Primes/Modular Arithmetic for a good, yet simple description.
Figure 1: Bob knows Alice's public key and uses it to encrypt the message. Alice uses her private key to decrypt the message.
Public keys are openly available for anybody to see, but private keys are not. The receiving site makes his public key available to the message sender, or by his making use of public directories. For each message transmission the sender uses this key to make the code. In this way only the private key of the recipient will decrypt it. A worked example has been provided in the text below, and the basic process can be seen in Figure 1.
In fact, the two keys used for public key encryption form a reversible function. You could encrypt with the private key and decrypt with the public key if the system designers had otherwise intended it. Of course, for less public use the public keys could just as easily be treated as secret also. This reversible nature of the key pair is useful in testing digital certificates, where the issuer encrypts a certificate with his private key so that the recipient can then use his freely available public key to test it's authenticity.
The numbers used are made deliberately very large, and this makes the task of obtaining the private key from the public key too difficult for a hacker. It involves the factorization of very large numbers, and is very time consuming.
Such systems, although imperfect, are nonetheless useful provided that the time to break them far exceeds the period for which the data is of any interest. The estimated time to break some such codes is many thousands of years.
Signed digital certificates help certify the identity of user sites when delivering public keys. Browsers take steps to confirm their validity.
The main advantage of the public key system is that there is a low administrative burden. Everything needed to send a message to a site is available in a public directory or is sent openly as a part of setting up the link.
The main disadvantage of public key cryptography is that it is too slow for modern internet use. Because of this, the internet most often uses symmetric encryption for the main task; (a different method that uses a common key for both encryption and decryption); it simply uses public key methods to conceal the symmetric keys while they are being sent to the far end.
There are several methods that hackers use to break coding:
The brute force cracking of a key refers to trying every possible combination of private key while testing it against the relevant cyphertext. Such testing is time consuming, because a dictionary check or human intervention is needed at each iteration to decide whether or not plain language has emerged. Also, the numbers are very large, so this method is rarely of much interest.
A mathematical attack refers to the finding of the two prime numbers, the product of which makes the modulus of the publicly available key. If these can be found then it simplifies the finding of the private key (more later); this method has the advantage that computers can be left to the task without much intervention. At the time of writing (2014) the record for breaking a key by mathematical attack is by Lenstra et al, on 12 December 2009, when an RSA-768 bit modulus (232 decimal digits) was factored using a method called the General Number Field Sieve (GNFS). The process required two years of collaboration and many hundreds of computing machines. (see: http://eprint.iacr.org/2010/006.pdf) Today most encryption keys in use are much bigger than the one that was broken, and a 1024 or 2048-bit key in an SSL certificate is still considered fairly safe against a mathematical attack. Note that the difficulty of breaking such a key increases exponentially with the key length.
The history of successful intrusions has not involved code breaking however, but the hacking of the servers for their data and private keys. Other exploits have relied on the security omissions of individuals, or defective programming. For example, a recent SSL exploit, (2000-2014?), has involved accessing data, not by code breaking, but by a programming flaw that allows the sender to download blocks of memory content from the destination's server. The intention in SSL is to allow some text from the recipient's server to be returned as proof of message receipt and successful decryption. For this purpose the sender can specify the length of text to return, usually a header, and in any case less than 64Kbits in length. The core of the flaw was that if a very short message was sent but the sender asked for a larger block to be returned than was sent, the faulty program would oblige, so returning data that included other secure material from memory. Repeating this process every few seconds allowed a hacker to accumulate a large data block. The matter is stated to have been since corrected, but is said to have been available to any who knew of it for a period of about four years.
Making Site B's PUBLIC Key[edit]
A public key is available to all, and is used to encrypt messages that are being sent to the key's owner.
Each site's computer produces two very large prime numbers, and since they are the basis of all that follows, these numbers are never revealed to any other. (Prime numbers are those that have no factors other than themselves or unity).
These two numbers are multiplied together to produce the modulus used in all of that site's calculations. The main public key is also derived from these primes, and determines the exponent to which the plain language numbers will be raised.
This public key is available in directories and from certificate authorities, so when the SENDER wants to encrypt a message by public key cryptography he can easily use the recipient's public key (and modulus) to do it. Each site's public key set can be made to be almost certainly different from every other.
To illustrate the point for an intending recipient, let us make a simple example with the large prime numbers replaced with very small ones.
Say the two secretly held prime numbers are:
p = 5 , q = 11
Then the modulus of the arithmetic that will be used is given by their product:
m = 5 x 11 = 55 (the modulus of the arithmetic to use)
The encryption key can be found as follows: First, using the two prime numbers, calculate the function:
f(n) = (p-1) x (q-1)
∵ p = 5 and q = 11
∴ f(n) = (5-1) x (11-1)
∴ f(n) = 40
then,
Select ANY number that is relatively prime to f(n) and less than it.
(Two numbers are said to be relatively prime when they share no common factors other than one. This term is also referred to as mutually prime, or coprime ).
The possible choices become:
3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, and 39.
Say we select the public encrypt exponent = 7
The receiving site's PUBLIC key can then be safely given to the world as :
(7, 55) as (encryption exponent, modulus)
(In practice the numbers would be very much larger)
The actual size of the numbers used is very large. For example, for a 1024-bit RSA encryption, this number is the size in bits of the modulus; this is equivalent to a decimal number of about 308 digits, or 256 hex digits. The public exponent most often chosen has an integer value of 65537. This exponent is chosen because it produces faster encryption than some other selections; that is, because of its large zero count in the binary form (10000000000000001), it lends itself to fast processing with binary shifting methods. It is known elsewhere as Fermat number F4. Despite this preference for the same exponent, recall that the other part of the public key set is the modulus, and that will differ between users based on the very large number of primes available.
Making Site B's Private KEY[edit]
Used by Site B when decrypting messages that were sent to them, encrypted using Site B's public key.
The private key pair is used to decrypt messages, and this key will only work if the public key of the same site was used to encrypt the message. That is to say, Site B's public key is obtained from a directory, then used by Site A to encrypt a message for them. When the message gets to Site B, Site B uses its own private key for decryption.
Continuing with the simple example above, the private key of Site B is made from its public key as follows.
private decrypt exponent = (public encrypt exponent)-1 Mod f(n)
∵ public encrypt exponent = 7 , and f(n) = 40
∴ (private decrypt exponent x 7) Mod 40 = 1
∴ private decrypt exponent = 23
The Site B PRIVATE key pair is then:
(23,55) as (decryption exponent, modulus)
It will have been noted by some that the same number can result for both the encrypt and decrypt exponents. This particular case must be avoided by deliberate testing since a hacker would likely test for this possibility early in the process of an attack. In the above examples, this would have been the case if 9, 11, 21, 33 or 39 were chosen for the public key instead of some other. Lest it be thought that anticipation of this error is simple, notice that even in this set that both coprimes that are themselves prime (eg; leading to: 11 * 11 = 1 mod 40), and those that are coprime but not in themselves prime (eg; 9, 21, 33, and 39), can all produce this insecure state of affairs.
With the use of long primes, m the modulus (their product), is very much longer, but it should be apparent that an intending hacker could still obtain the private key if he were able to find the two secret primes as a starting point. Both the public key and the modulus to use with it are given to all who require it for encryption, so the burden of a mathematical attack reduces to the difficulty of factoring the modulus into these two secret primes. For the simple example shown above (m=55) this task is very simple, but for a very large number this effort is prohibitively long.
The native format in which the private key is delivered is in fact base-64, (a character set that needs only 6 bits per character, instead of the 4 for hex or the 7 for ASCI character codes). Unlike the public key string, the layout of a practical private key string for a 1024-bit RSA encryption contains the private key details, the public key details, and the secret numbers used in their making, as well as various other numbers and headers. The private key exponent, unlike the public exponent, is quite long, and is the equivalent of 256 hex digits in length. The secret primes are each 128 hex numbers in length. The decimal equivalent lengths are 308 digits for the private exponent (and the modulus), and 154 digits for each of the secret numbers.
Factoring the Modulus[edit]
Hackers who intend to factor the modulus without any other algorithm to assist, can simply divide the modulus by a succession of increasing primes until a zero remainder results. Then the two primes would be known. However the number of primes is also very high in such a large modulus. In general the following approximation, refered to as The Prime Number Theorem, gives the number of primes in the number x as:
number of primes ≅ x/(logx - 1)
now a 64 bit space is equivalent to about 20 digits
∴ number of primes ≅ 4 * 1017
then assuming 1 million calculations per second, (a wildly optimistic assumption for most):
the time to test all the primes ≅ 13,500 years
The example here was limited to 64 bits because the more representative figures, 128, 256, 512, 1024, and 2048-bit calculations are too big for most calculators. See The Math Behind Estimations to Break a 2048-bit Certificate by DigiCert for more details.
This example does not consider the use of improved methods for factoring, and these appear frequently in the literature. At present, (2014), the best of these is considered to be the General Number Field Sieve (GNFS), used to establish the record in December 2009.
To expand a little on the subject of improved methods, it will be apparent that starting with lists of tabulated primes speeds up the process. This, and the production of calculated product tables against their future need also allows much faster processing than would otherwise be possible by calculating on the fly. Because clearly, for a large set of such cracking problems, half of the solutions will lie in the first half of the trial values and half of them in the second, it has become the habit to express the expected time to solution for half of the set as opposed to the whole number implied by the Fundamental Theorem of Alebra. (FTOA).
Encryption with B's Public Key[edit]
Assume that the public key pair belong to a Site B. Assume also that a plain language character represented by the number '2' is to be encrypted by Site A and sent to the recipient Site B: Site A uses Site B's public key pair to do so.
Assume plaintext=2
cyphertext = plaintext public encrypt exponent Mod n
∵ public encrypt exponent =7, and modulus = 55
∴ cyphertext = 27 Mod 55 = 128 Mod 55
∴ cyphertext = 18
With the very small numbers used in the example the cracking of the code would be relatively simple. But for very large values of primes p and q, and without knowing the private key value, the burden becomes very difficult. In some cases the task would involve an unreasonable time even for a very large number of computers.
Public key encryption does not disguise the relative frequency of the characters used. This is considered a failing in such systems since it improves the chances of cracking the code. So, the plaintext characters are arranged into groups before encryption to hide their natural frequencies of use; the groups are very large, the limit being that the size of a number encrypted must be smaller than the modulus in use.
Decryption with B's Private Key[edit]
Decryption using the above specific example is acheived as follows: For the received cyphertext = 18
With cyphertext=18 from previous section
Plaintext = cyphertextprivate decrypt exponent Mod n
∵ private decrypt exponent = 23, and modulus = 55
∴ Plaintext = 1823 Mod 55 = 74347713614021927913318776832 Mod 55
∴ Plaintext = 2 (You can only just confirm this with the Windows scientific calculator)
Notice that the plain language value of 2 has been recovered, which is the required result.
And then the hacker will come, and will try to decode it using other key. For example 3: For the received cyphertext = 18
With cyphertext=18 from previous section
Plaintext = cyphertextprivate decrypt exponent Mod n
∵ private decrypt exponent = 3, and modulus = 55
∴ Plaintext = 183 Mod 55 = 5832 Mod 55
∴ Plaintext = 2 (You can only just confirm this with the Windows scientific calculator)
Note that every (N^7|55)^3|55 == (N^7|55)^23|55 (someone should review the above private key generation)
The Internet Speed Compromise[edit]
Because public key encryption and decryption is so very slow, it is unsuitable in its native form for internet use. In fact, asymmetric public key encryption is used for only a small part of internet communications. Such systems are hybrid. The summary of the method used is as follows:
The text to be transmitted securely will be encrypted, not by public key cryptography, but by using SYMMETRIC key encryption. This is typically a 128 bit cipher, but can be greater. Symmetric key methods need both sites to use the same key. To do this one site must at some stage originate the key then send a copy of it to the other.
This SYMMETRIC key, is not sent to the far end openly but is kept safe by first encrypting it using PUBLIC key methods. The public key of the destination site is used for this.
The recipient uses his PRIVATE key to decrypt this cyphertext, and to recover the SYMMETRIC key value. He then decrypts the main symmetric ciphertext with it.
The symmetric encryption key is discarded at the end of the current session, and the asymmetric public key may or may not be discarded, depending on the system in use. A short lifetime for the key reduces the chances of a successful key recovery during cyber-attacks and the subsequent decoding of recorded traffic at a later date. With this in mind, it might be that short sessions are more secure than long ones, provided of course that discarded means the complete removal from memory, and not just the ubiquitous delete.
The systems currently in use for internet browsers are Transport Layer Security (TLS) and its predecessor, Secure Sockets Layer (SSL). A complete description of these is available at Wikipedia's Secure Sockets Layer.
Note that in a duplex system, that is, the usual kind that sends in both directions, there will be two such procedures. One originated at each end. The key sets used for send and receive, for both asymmetric and symmetric encryption systems are all different.
Message Authentication[edit]
Security breaks down if outsiders can change the message in transit, or if they mis-represent themselves right from the start. In an attempt to overcome these risks digital certificates were devised. In a further attempt to ensure that the certificates were from the place respected by the users, the certificates were given digital signatures. One such method among many is the Digital Signature Algorithm (DSA), the basis of the Digital Signature Standard (DSS).
These certificates are not just simple text messages, which of course could be imitated, but use calculated values based on the content of a message. The entire basis of certification depends both on the designed properties of these hash algorithms and on the integrity of those who assert their worth. Their properties include:
Sensitivity: They are very sensitive. A very small change in a hash algorithm's input always creates a very large change in its output value.
Specificity: They are very specific. Although it depends on the hash algorithm used, there is very little chance that two different inputs could ever produce the same output. When this happens, say once in many billions, it is referred to as a collision.
Opacity: An input value cannot be found from a output value. This is because of the great complexity of the algorithm and in particular, because of the liberal use of modular arithmetic's one-way functions.
Secrecy: Some hash algorithms are available for public use, but proprietary interests can make their own. Algorithms available for the use of most include MD5, SHA1, SHA2, SHA3, and others.MD5 has been broken. SHA1, the basis for much of the current certification, is deprecated in its use for more complexity.
The hash value is calculated by the sender and compared with one calculated at the receiving end, where the two must match for acceptance. Like encryption itself, hash values are too laborious to reverse engineer, that is to say, new or changed messages could not be made by outsiders to represent an existing hash value within any useful time period. Because of this they provide a basis upon which to verify that a message's contents were not changed since the certificate was issued.
Certificates themselves are tested against known root certificates within the browser store, to ensure that the certificates are from a known reliable source. If certificates are secret-signed with a private key known only to the issuing authority, then validation of the certificate can be made by decrypting the signature with its public key. That is to say, because the process is reversible, validation of the source can be made.
The actual process used for these tasks is more complex than is implied in summary, involving many long-bit calculations, but the strength of the system is unlikely to satisfy the skeptical until the sums are seen. Refer to the pdf file How Encryption and Digital Signatures Work and read the section An Example of a Digital Signature Mechanism for such a description.
The process of testing certificates and other matters are in any case summarized by browsers for their users. Browsers will indicate clearly whether or not they consider a connection to be secure. The most common of these indications includes an added padlock somewhere on the screen and the modification of the site's http address heading to read https. Some browsers such as Opera add other information such as color coding to represent the levels of security.
RSA Algorithm
The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977 [RIVE78]. The basic technique was first discovered in 1973 by Clifford Cocks [COCK73] of CESG (part of the British GCHQ) but this was a secret until 1997. The patent taken out by RSA Labs has expired.
The RSA cryptosystem is the most widely-used public key cryptography algorithm in the world. It can be used to encrypt a message without the need to exchange a secret key separately.
The RSA algorithm can be used for both public key encryption and digital signatures. Its security is based on the difficulty of factoring large integers.
Party A can send an encrypted message to party B without any prior exchange of secret keys. A just uses B's public key to encrypt the message and B decrypts it using the private key, which only he knows. RSA can also be used to sign a message, so A can sign a message using their private key and B can verify it using A's public key.
Key Generation Algorithm
This is the original algorithm.
Generate two large random primes, p and q, of approximately equal size such that their product n=pq is of the required bit length, e.g. 1024 bits. [See note 1].
Compute n=pq and ϕ=(p−1)(q−1). [See note 6].
Choose an integer e, 1<e<ϕ, such that gcd(e,ϕ)=1. [See note 2].
Compute the secret exponent d, 1<d<ϕ, such that ed≡1modϕ. [See note 3].
The public key is (n,e) and the private key (d,p,q). Keep all the values d, p, q and ϕ secret. [Sometimes the private key is written as (n,d) because you need the value of n when using d. Other times we might write the key pair as ((N,e),d).]
n is known as the modulus.
e is known as the public exponent or encryption exponent or just the exponent.
d is known as the secret exponent or decryption exponent.
A practical key generation algorithm
Incorporating the advice given in the notes below, a practical algorithm to generate an RSA key pair is given below. Typical bit lengths are k=1024,2048,3072,4096,..., with increasing computational expense for larger values. You will not go far wrong if you choose e as 65537 (=0x10001) in step (1).
Algorithm: Generate an RSA key pair.
INPUT: Required modulus bit length, k.
OUTPUT: An RSA key pair ((N,e),d) where N is the modulus, the product of two primes (N=pq) not exceeding k bits in length; e is the public exponent, a number less than and coprime to (p−1)(q−1); and d is the private exponent such that ed≡1mod(p−1)(q−1).
Select a value of e from 3,5,17,257,65537
repeat
p ← genprime(k/2)
until (pmode)≠1
repeat
q ← genprime(k - k/2)
until (qmode)≠1
N ← pq
L ← (p-1)(q-1)
d ← modinv(e, L)
return (N,e,d)
The function genprime(b) returns a prime of exactly b bits, with the bth bit set to 1. Note that the operation k/2 is integer division giving the integer quotient with no fraction.
If you've chosen e=65537 then the chances are that the first prime returned in steps (3) and (6) will pass the tests in steps (4) and (7), so each repeat-until loop will most likely just take one iteration. The final value of N may have a bit length slightly short of the target k. This actually does not matter too much (providing the message m is always < N), but some schemes require a modulus of exact length. If this is the case, then just repeat the entire algorithm until you get one. It should not take too many goes. Alternatively, use the trick setting the two highest bits in the prime candidates described in note 1.
Encryption
Sender A does the following:-
Obtains the recipient B's public key (n,e).
Represents the plaintext message as a positive integer m with 1<m<n [see note 4].
Computes the ciphertext c=memodn.
Sends the ciphertext c to B.
Decryption
Recipient B does the following:-
Uses his private key (n,d) to compute m=cdmodn.
Extracts the plaintext from the message representative m.
Digital signing
Sender A does the following:-
Creates a message digest of the information to be sent.
Represents this digest as an integer m between 1 and n−1 [See note 5].
Uses her private key (n,d) to compute the signature s=mdmodn.
Sends this signature s to the recipient, B.
Signature verification
Recipient B does the following (older method):-
Uses sender A's public key (n,e) to compute integer v=semodn.
Extracts the message digest H from this integer.
Independently computes the message digest H′ of the information that has been signed.
If both message digests are identical, i.e. H=H′, the signature is valid.
More secure method:-
Uses sender A's public key (n,e) to compute integer v=semodn.
Independently computes the message digest H′ of the information that has been signed.
Computes the expected representative integer v′ by encoding the expected message digest H′.
If v=v′, the signature is valid.
Notes on practical applications
To generate the primes p and q, generate a random number of bit length k/2 where k is the required bit length of the modulus n; set the low bit (this ensures the number is odd) and set the two highest bits (this ensures that the high bit of n is also set); check if prime (use the Rabin-Miller test); if not, increment the number by two and check again until you find a prime. This is p. Repeat for q starting with a random integer of length k−k/2. If p<q, swop p and q (this only matters if you intend using the CRT form of the private key). In the extremely unlikely event that p=q, check your random number generator! Alternatively, instead of incrementing by 2, just generate another random number each time.
There are stricter rules in ANSI X9.31 to produce strong primes and other restrictions on p and q to minimise the possibility of certain techniques being used against the algorithm. There is much argument about this topic. It is probably better just to use a longer key length.
In practice, common choices for e are 3, 5, 17, 257 and 65537 (216+1). These particular values are chosen because they are primes and make the modular exponentiation operation faster, having only two bits of value 1.
--> Aside: These five numbers are the first five Fermat numbers, referred to as F0 to F4, where Fx=22x+1. Just be careful, these first five Fermat numbers are prime ("Fermat primes"), but the numbers F5and above are not prime. For example, F5=4294967297=641×6700417.
The usual choice for e is F4=65537 = 0x10001. Also, having chosen e, it is simpler to test whether gcd(e,p−1)=1 and gcd(e,q−1)=1 while generating and testing the primes in step 1. Values of p or q that fail this test can be rejected there and then.
Even better: if e is an odd prime then you can do the less-expensive test (pmode)≠1 instead of gcd(p−1,e)=1.
Why is that? If e is an odd prime then gcd(p−1,e)≠1 if and only if p−1 is a multiple of e. If p−1 is a multiple of e then p−1≡0(mode) or p≡1(mode). Conversely, if p≢1(mode) then p−1≢0(mode) and p−1 is not a multiple of e. So gcd(p−1,e)=1.
To compute the value for d, use the Extended Euclidean Algorithm to calculate d=e−1modϕ, also written d=(1/e)modϕ. This is known as modular inversion. Note that this is not integer division. The modular inverse d is defined as the integer value such that ed=1modϕ. It only exists if e and ϕ have no common factors.
When representing the plaintext octets as the representative integer m, it is important to add random padding characters to make the size of the integer m large and less susceptible to certain types of attack. If m = 0 or 1 or n-1 there is no security as the ciphertext has the same value. For more details on how to represent the plaintext octets as a suitable representative integer m, see PKCS#1 Schemes below or the reference itself [PKCS1]. It is important to make sure that m<n otherwise the algorithm will fail. This is usually done by making sure the first octet of m is equal to 0x00.
Decryption and signing are identical as far as the mathematics is concerned as both use the private key. Similarly, encryption and verification both use the same mathematical operation with the public key. That is, mathematically, for m<n,
m=(memodn)dmodn=(mdmodn)emodn
However, note these important differences in implementation:-
The signature is derived from a message digest of the original information. The recipient will need to follow exactly the same process to derive the message digest, using an identical set of data.
The recommended methods for deriving the representative integers are different for encryption and signing (encryption involves random padding, but signing uses the same padding each time).
The original definition of RSA uses the Euler totient function ϕ(n)=(p−1)(q−1). More recent standards use the Charmichael function λ(n)=lcm(p−1,q−1) instead. λ(n) is smaller than ϕ(n) and divides it. The value of d′ computed by d′=e−1modλ(n) is usually different from that derived by d=e−1modϕ(n), but the end result is the same. Both dand d′ will decrypt a message memodn and both will give the same signature value s=mdmodn=md′modn. To compute λ(n), use the relation
λ(n)=(p−1)(q−1)gcd(p−1,q−1).
You might ask if there is a way to find the factors of n given just d and e. This is possible.
For more details, see our page RSA: how to factorize N given d.
Summary of RSA
n=pq, where p and q are distinct primes.
ϕ=(p−1)(q−1)
e<n such that gcd(e,ϕ)=1
d=e−1modϕ
c=memodn,1<m<n
m=cdmodn
For more on the theory and mathematics behind the algorithm, see the RSA Theory page.
Key length
When we talk about the key length of an RSA key, we are referring to the length of the modulus, n, in bits. The minimum recommended key length for a secure RSA transmission is currently at least 1024 bits. A key length of 512 bits is no longer considered secure, although cracking it is still not a trivial task for the likes of you and me. The longer your information needs to be kept secure, the longer the key you should use. Keep up to date with the latest recommendations in the security journals.
There is one small area of confusion in defining the key length. One convention is that the key length is the position of the most significant bit in n that has value '1', where the least significant bit is at position 1. Equivalently, key length = ⌈log2(n+1))⌉, where ⌈x⌉ is the ceiling function, the least integer greater than or equal to x. The other convention, sometimes used, is that the key length is the number of bytes needed to store n multiplied by eight, i.e. ⌈log256(n+1)⌉×8.
The key used in the RSA Example paper [KALI93] is an example. The modulus is represented in hex form as
0A 66 79 1D C6 98 81 68 DE 7A B7 74 19 BB 7F B0
C0 01 C6 27 10 27 00 75 14 29 42 E1 9A 8D 8C 51
D0 53 B3 E3 78 2A 1D E5 DC 5A F4 EB E9 94 68 17
01 14 A1 DF E6 7C DC 9A 9A F5 5D 65 56 20 BB AB
The most significant byte 0x0A in binary is 00001010'B. The most significant bit is at position 508, so its key length is 508 bits. On the other hand, this value needs 64 bytes to store it, so the key length could also be referred to by some as 64 x 8 = 512 bits. We prefer the former method. You can get into difficulties with the X9.31 method for signatures if you use the latter convention.
Minimum key lengths
The following table is taken from NIST's Recommendation for Key Management [NIST-80057]. It shows the recommended comparable key sizes for symmetrical block ciphers (AES and Triple DES) and the RSA algorithm. That is, the key length you would need to use to have comparable security.
Symmetric key algorithmComparable RSA key lengthComparable hash functionBits of security
2TDEA*1024SHA-180
3TDEA2048SHA-224112
AES-1283072SHA-256128
AES-1927680SHA-384192
AES-25615360SHA-512256
* 2TDEA is 2-key triple DES - see What's two-key triple DES encryption.
Note just how huge (and impractical) an RSA key needs to be for comparable security with AES-192 or AES-256 (although these two algorithms have had some weaknesses exposed recently; AES-128 is unaffected).
The above table is a few years old now and may be out of date. Existing cryptographic algorithms only get weaker as attacks get better.
Computational Efficiency and the Chinese Remainder Theorem (CRT)
Key generation is only carried out occasionally and so computational efficiency is less of an issue.
The calculation y=xemodn is known as modular exponentiation and one efficient method to carry this out on a computer is the binary left-to-right method. To solve, let e be represented in base 2 as
e=ek−1ek−2…e1e0
where ek−1 is the most significant non-zero bit and bit e0 the least.
set y = x
for bit j = k - 2 downto 0
begin
y = y * y mod n /* square */
if e(j) == 1 then
y = y * x mod n /* multiply */
end
return y
The time to carry out modular exponentation increases with the number of bits set to one in the exponent e. For encryption, an appropriate choice of e can reduce the computational effort required to carry out the computation of c=memodn. Popular choices like 3, 17 and 65537 are all primes with only two bits set: 3 = 0011'B, 17 = 0x11, 65537 = 0x10001.
The bits in the decryption exponent d, however, will not be so convenient and so decryption using the standard method of modular exponentiation will take longer than encryption. Don't make the mistake of trying to contrive a small value for d; it will not be secure.
An alternative method of representing the private key uses the The Chinese Remainder Theorem (CRT).
For an explanation of how the CRT is used with RSA, see Using the CRT with RSA.
The private key is represented as a quintuple (p, q, dP, dQ, and qInv), where p and q are prime factors of n, dP and dQ are known as the CRT exponents, and qInv is the CRT coefficient. The CRT method of decryption is about four times faster overall than calculating m=cdmodn. The extra values for the private key are:-
dP = (1/e) mod (p-1)
dQ = (1/e) mod (q-1)
qInv = (1/q) mod p where p > q
where the (1/e) notation means the modular inverse (see note 3 above). These values are pre-computed and saved along with p and q as the private key. To compute the message m given c do the following:-
m1 = c^dP mod p
m2 = c^dQ mod q
h = qInv(m1 - m2) mod p
m = m2 + hq
Even though there are more steps in this procedure, the modular exponentation to be carried out uses much shorter exponents and so it is less expensive overall.
[2008-09-02] Chris Becke has pointed out that most large integer packages will fail when computing h if m1 < m2. This can be easily fixed by computing
h = qInv(m1 + p - m2) mod p
or, alternatively, as we do it in our BigDigits implementation of RSA,
if (bdCompare(m1, m2) < 0)
bdAdd(m1, m1, p);
bdSubtract(m1, m1, m2);
/* Let h = qInv ( m_1 - m_2 ) mod p. */ bdModMult(h, qInv, m1, p);
A very simple example of RSA encryption
This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 45 55 can probably even do it by hand).
Select primes p=11, q=3.
n = pq = 11.3 = 33
phi = (p-1)(q-1) = 10.2 = 20
Choose e=3
Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
and check gcd(e, q-1) = gcd(3, 2) = 1
therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
Compute d such that ed ≡ 1 (mod phi)
i.e. compute d = (1/e) mod phi = (1/3) mod 20
i.e. find a value for d such that phi divides (ed-1)
i.e. find d such that 20 divides 3d-1.
Simple testing (d = 1, 2, ...) gives d = 7
Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.
Public key = (n, e) = (33, 3)
Private key = (n, d) = (33, 7).
This is actually the smallest possible value for the modulus n for which the RSA algorithm works.
Now say we want to encrypt the message m = 7,
c=memodn=73mod33=343mod33=13.
Hence the ciphertext c = 13.
To check decryption we compute
m′=cdmodn=137mod33=7.
Note that we don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that
a=bcmodn=(bmodn)⋅(cmodn)modn
so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value.
One way of calculating m' is as follows:-
Note that any number can be expressed as a sum of powers of 2. In particular 7 = 4 + 2 + 1.
So first compute values of 132,134,138,… by repeatedly squaring successive values modulo 33.
132=169≡4,134=4.4=16,138=16.16=256≡25.
Then, since 7 = 4 + 2 + 1, we have m′=137=13(4+2+1)=134.132.131
≡16×4×13=832≡7(mod33)
Now if we calculate the ciphertext c for all the possible values of m (0 to 32), we get
m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16c 0 1 8 27 31 26 18 13 17 3 10 11 12 19 5 9 4m 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32c 29 24 28 14 21 22 23 30 16 20 15 7 2 6 25 32
Note that all 33 values of m (0 to 32) map to a unique code c in the same range in a sort of random manner. In this case we have nine values of m that map to the same value of c - these are known as unconcealed messages. m = 0, 1 and n-1 will always do this for any n, no matter how large. But in practice, these shouldn't be a problem when we use large values for n in the order of several hundred bits.
If we wanted to use this system to keep secrets, we could let A=2, B=3, ..., Z=27. (We specifically avoid 0 and 1 here for the reason given above). Thus the plaintext message "HELLOWORLD" would be represented by the set of integers m1,m2,…
(9,6,13,13,16,24,16,19,13,5)
Using our table above, we obtain ciphertext integers c1,c2,…
(3,18,19,19,4,30,4,28,19,26)
Note that this example is no more secure than using a simple Caesar substitution cipher, but it serves to illustrate a simple example of the mechanics of RSA encryption.
Remember that calculating memodn is easy, but calculating the inverse c−emodn is very difficult, well, for large n's anyway. However, if we can factor n into its prime factors p and q, the solution becomes easy again, even for large n's. Obviously, if we can get hold of the secret exponent d, the solution is easy, too.
A slightly less simple example of the RSA algorithm
This time, to make life slightly less easy for those who can crack simple Caesar substitution codes, we will group the characters into blocks of three and compute a message representative integer for each block. Please note that this method is not secure in any way. It just shows another example of the mechanism of RSA with small numbers.
For this example, to keep things simple, we'll limit our characters to the letters A to Z and the space character.
ATTACK AT SEVEN = ATT ACK _AT _SE VEN
In the same way that any decimal number can be represented uniquely as the sum of powers of ten, e.g. 135=1×102+3×101+5,
we can represent our blocks of three characters as the sum of powers of 27 using SPACE=0, A=1, B=2, C=3, .. E=5, .. K=11, .. N=14, .. S=19, T=20, .. V=22, ..., Z=26.
ATT ⇒ 1 x 27^2 + 20 x 27^1 + 20 = 1289
ACK ⇒ 1 x 27^2 + 3 x 27^1 + 11 = 821
_AT ⇒ 0 x 27^2 + 1 x 27^1 + 20 = 47
_SE ⇒ 0 x 27^2 + 19 x 27^1 + 5 = 518
VEN ⇒ 22 x 27^2 + 5 x 27^1 + 14 = 16187
Using this system of integer representation, the maximum value of a block (ZZZ) is 273−1=19682, so we require a modulus n greater than this value.
We choose e = 3
We select primes p=173 and q=149 and check
gcd(e, p-1) = gcd(3, 172) = 1 ⇒ OK
gcd(e, q-1) = gcd(3, 148) = 1 ⇒ OK.
Thus we have n=pq=173×149=25777, and
ϕ=(p−1)(q−1)=172×148=25456.
We compute d=e−1modϕ=3−1mod25456=16971.
Note that ed=3×16971=50913=2×25456+1
That is, ed≡1mod25456≡1modϕ
Hence our public key is (n, e) = (25777, 3) and our private key is (n, d) = (25777, 16971). We keep the values of p, q, d and φ secret.
To encrypt the first integer that represents "ATT", we have
c=memodn=12893mod25777=18524.
Overall, our plaintext ATTACK AT SEVEN is represented by the sequence of five integers m1,m2,m3,m4,m5:
m_i = (1289, 821, 47, 518, 16187)
We compute corresponding ciphertext integers ci=meimodn, (which is still possible by using a calculator, honest):
c1=12893mod25777=18524c2=8213mod25777=7025c3=473mod25777=715c4=5183mod25777=2248c5=161873mod25777=24465
We can send this sequence of integers, ci, to the person who has the private key.
c_i = (18524, 7025, 715, 2248, 24465)
We can compute the inverse of these ciphertext integers using m=cdmodn to verify that the RSA algorithm still holds. However, this is now outside the realm of hand calculations.
To help you carry out these modular arithmetic calculations, download our free modular arithmetic command line programs.
For example, to compute 1852416971mod25777, use the bd_modexp command:
bd_modexp 18524 16971 25777
18524^16971 mod 25777 = 1289
You should get the results:
m1=1852416971mod25777=1289m2=702516971mod25777=821m3=71516971mod25777=47m4=224816971mod25777=518m5=2446516971mod25777=16187
To convert these integers back to the block of three letters, do the following. For example, given m = 16187,
16187 ÷ 27^2 = 16187 ÷ 729 = 22 rem 149, 22 → 'V'
149 ÷ 27^1 = 149 ÷ 27 = 5 rem 14, 5 → 'E'
14 ÷ 27^0 = 14 ÷ 1 = 14 rem 0, 14 → 'N'
Hence the integer m = 16187 represents the string "VEN".
Similarly, m = 47 is encoded as follows:
47 ÷ 27^2 = 0 rem 47, 0 → SPACE;
47 ÷ 27^1 = 1 rem 20, 1 → 'A';
20 ÷ 27^0 = 20 rem 0, 20 → 'T'
giving the string "_AT".
Question: Why can't we use this method of encoding integers into blocks of three letters to encode the ciphertext?
A caution about this example
Note that this example is a very insecure method of encryption and should not be used in practice. We can easily factorize the modulus and hence break the cipher.
Factorising a small RSA modulus
Starting with the knowledge that the modulus 25777 is the product of exactly two distinct prime numbers, and that one of these must be less than its integer square root (why?), a little testing of suitable candidates from a table of prime numbers will get you the answer pretty quickly.
Given n = 25777, compute √25777 = 160.55, and then work downwards through the prime numbers < 160, i.e. (157, 151, 149, 139, ...), and try to divide into n in turn:
157: 25777 / 157 = 164 remainder 29, so not a factor;
151: 25777 / 151 = 170 remainder 107, so not a factor;
149: 25777 / 149 = 173 exactly, so we have it.
You could also write a simple computer program to factor n that just divides it by every odd number starting from 3 until it either finds an exact factor or stops when it reaches a number greater than the square root of n.
A real example
In practice, we use a modulus of size in the order of 1024 bits. That is a number over 300 decimal digits long. One example is
n =
11929413484016950905552721133125564964460656966152763801206748195494305685115033
38063159570377156202973050001186287708466899691128922122454571180605749959895170
80042105263427376322274266393116193517839570773505632231596681121927337473973220
312512599061231322250945506260066557538238517575390621262940383913963
This is composed of the two primes
p =
10933766183632575817611517034730668287155799984632223454138745671121273456287670
008290843302875521274970245314593222946129064538358581018615539828479146469
q =
10910616967349110231723734078614922645337060882141748968209834225138976011179993
394299810159736904468554021708289824396553412180514827996444845438176099727
With a number this large, we can encode all the information we need in one big integer. We put our message into an octet string and then convert to a large integer.
Also, rather than trying to represent the plaintext as an integer directly, we generate a random session key and use that to encrypt the plaintext with a conventional, much faster symmetrical algorithm like Triple DES or AES-128. We then use the much slower public key encryption algorithm to encrypt just the session key.
The sender A then transmits a message to the recipient B in a format something like this:-
Session key encrypted with RSA = xxxx
Plaintext encrypted with session key = xxxxxxxxxxxxxxxxx
The recipient B would extract the encrypted session key and use his private key (n,d) to decrypt it. He would then use this session key with a conventional symmetrical decryption algorithm to decrypt the actual message. Typically the transmission would include in plaintext details of the encryption algorithms used, padding and encoding methods, initialisation vectors and other details required by the recipient. The only secret required to be kept, as always, should be the private key.
If Mallory intercepts the transmission, he can either try and crack the conventionally-encrypted plaintext directly, or he can try and decrypt the encryped session key and then use that in turn. Obviously, this system is as strong as its weakest link.
When signing, it is usual to use RSA to sign the message digest of the message rather than the message itself. A one-way hash function like SHA-1 or SHA-256 is used. The sender A then sends the signed message to B in a format like this
Hash algorithm = hh
Message content = xxxxxxxxx...xxx
Signature = digest signed with RSA = xxxx
The recipient will decrypt the signature to extract the signed message digest, m; independently compute the message digest, m′, of the actual message content; and check that m and m′ are equal. Putting the message digest algorithm at the beginning of the message enables the recipient to compute the message digest on the fly while reading the message.
CAUTION: We cannot emphasise enough that you never use the unadorned versions of RSA described in the simple examples above. You must use a proper scheme like PCKS#1 below. In particular when encrypting a message, you must use random padding.
PKCS#1 Schemes
The most common scheme using RSA is PKCS#1 version 1.5 [PKCS1]. This standard describes schemes for both encryption and signing. The encryption scheme PKCS#1v1.5 has some known weaknesses, but these can easily be avoided. See Weaknesses in RSA below.
There is an excellent paper by Burt Kalinski of RSA Laboratories written in the early 1990s [KALI93] that describes in great detail everything you need to know about encoding and signing using RSA. There are full examples right down to listing out the bytes. OK, it uses MD2 and a small 508-bit modulus and obviously doesn't deal with refinements built up over the last decade to deal with more subtle security threats, but it's an excellent introduction.
The conventions we use here are explained below in Notation and Conventions.
Encryption using PKCS#1v1.5
Algorithm: Encryption using PKCS#1v1.5
INPUT: Recipient's RSA public key, (n, e), of length k = |n| bytes; data D (typically a session key) of length |D| bytes with |D|<=k-11.
OUTPUT: Encrypted data block of length k bytes
Form the k-byte encoded message block, EB,
EB = 00 || 02 || PS || 00 || D
where || denotes concatenation and PS is a string of k-|D|-3 non-zero randomly-generated bytes (i.e. at least eight random bytes).
Convert the byte string, EB, to an integer, m, most significant byte first,
m = StringToInteger(EB)
Encrypt with the RSA algorithm
c = m^e mod n
Convert the resulting ciphertext, c, to a k-byte output block, OB‡
OB = IntegerToString(c, k)
Output OB.
The conversions in steps (2) and (4) from byte string to large integer representative and back again may not be immediately obvious. Large integers and byte (bit) strings are conceptually different even though they may both be stored as arrays of bytes in your computer. See What is the difference between a bit string and an integer?
‡2012-05-23: Thanks to "dani torwS" for pointing out a typo in the formula.
Worked Example
Bob's 1024-bit RSA encryption key in hex format:
n=
A9E167983F39D55FF2A093415EA6798985C8355D9A915BFB1D01DA197026170F
BDA522D035856D7A986614415CCFB7B7083B09C991B81969376DF9651E7BD9A9
3324A37F3BBBAF460186363432CB07035952FC858B3104B8CC18081448E64F1C
FB5D60C4E05C1F53D37F53D86901F105F87A70D1BE83C65F38CF1C2CAA6AA7EB
e=010001
d=
67CD484C9A0D8F98C21B65FF22839C6DF0A6061DBCEDA7038894F21C6B0F8B35
DE0E827830CBE7BA6A56AD77C6EB517970790AA0F4FE45E0A9B2F419DA8798D6
308474E4FC596CC1C677DCA991D07C30A0A2C5085E217143FC0D073DF0FA6D14
9E4E63F01758791C4B981C3D3DB01BDFFA253BA3C02C9805F61009D887DB0319
A randomly-generated one-off session key for AES-128 might be
D=4E636AF98E40F3ADCFCCB698F4E80B9F
The encoded message block, EB, after encoding but before encryption, with random padding bytes shown in green,
0002257F48FD1F1793B7E5E02306F2D3228F5C95ADF5F31566729F132AA12009
E3FC9B2B475CD6944EF191E3F59545E671E474B555799FE3756099F044964038
B16B2148E9A2F9C6F44BB5C52E3C6C8061CF694145FAFDB24402AD1819EACEDF
4A36C6E4D2CD8FC1D62E5A1268F496004E636AF98E40F3ADCFCCB698F4E80B9F
After RSA encryption, the output is
3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5
8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621
EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E
609787ADCE055839829E0142C44B676D218111FFE69F9D41424E177CBA3A435B
The above hex data in C format.
Note that the output for encryption will be different each time (or should be!) because of the random padding used.
Encrypting a message
For a plaintext message, say,
PT="Hello world!"
that is, the 12 bytes in hex format,
PT=48656C6C6F20776F726C6421
Then, using the 128-bit session key from above,
KY=4E636AF98E40F3ADCFCCB698F4E80B9F
and the uniquely-generated 128-bit initialization vector (IV)
IV=5732164B3ABB6C4969ABA381C1CA75BA
the ciphertext using AES-128 in CBC mode with PKCS#5 padding is,
CT=67290EF00818827C777929A56BC3305B
The sender would then send a transmission to the recipient (in this case, Bob) including the following information in some agreed format
Recipient: Bob
Key Encryption Algorithm: rsaEncryption
Encrypted Key:
3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5
8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621
EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E
609787ADCE055839829E0142C44B676D218111FFE69F9D41424E177CBA3A435B
Content Encryption Algorithm: aes128-cbc
IV: 5732164B3ABB6C4969ABA381C1CA75BA
Encrypted Content:
67290EF00818827C777929A56BC3305B
The usual formats used for such a message are either a CMS enveloped-data object or XML, but the above summary includes all the necessary info (well, perhaps "Bob" might be defined a bit more accurately).
Cryptographic Message Syntax (CMS) [CMS] is a less-ambiguous version of the earlier PKCS#7 standard (also of the same name) and is designed to be used in S/MIME messages. CMS enveloped-data objects (yes, that's enveloped not encrypted) use ASN.1 and are encoded using either DER- or BER-encoding. (DER-encoding is a stricter subset of BER).
The terminology for CMS and ASN.1 may sound messy, but the end results are well-defined and universally-accepted. On the other hand, the XML cryptographic standards are, to be honest, a complete mess: see XML is xhite. Pretty Good Privacy (PGP) also has a format for RSA messages, although PGP stopped using RSA because of patent issues back in the 1990s.
Nothing, of course, stops you and your recipient from agreeing on your own format and using that. But be careful, even the experts get these things wrong and accidentally give away more than they realise.
Signing using PKCS#1v1.5
Algorithm: Signing using PKCS#1v1.5
INPUT: Sender's RSA private key, (n, d) of length k = |n| bytes; message, M, to be signed; message digest algorithm, Hash.
OUTPUT: Signed data block of length k bytes
Compute the message digest H of the message,
H = Hash(M)
Form the byte string, T, from the message digest, H, according to the message digest algorithm, Hash, as follows
HashT
MD530 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10 || H
SHA-130 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H
SHA-22430 2d 30 0d 06 09 60 86 48 01 65 03 04 02 04 05 00 04 1c || H
SHA-25630 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H
SHA-38430 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 || H
SHA-51230 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H
where T is an ASN.1 value of type DigestInfo encoded using the Distinguished Encoding Rules (DER).
Form the k-byte encoded message block, EB,
EB = 00 || 01 || PS || 00 || T
where || denotes concatenation and PS is a string of bytes all of value 0xFF of such length so that |EB|=k.
Convert the byte string, EB, to an integer m, most significant byte first,
m = StringToInteger(EB)
Sign with the RSA algorithm
s = m^d mod n
Convert the resulting signature value, s, to a k-byte output block, OB
OB = IntegerToString(s, k)
Output OB.
Worked Example
Alice's 1024-bit RSA signing key in hex format:
n=
E08973398DD8F5F5E88776397F4EB005BB5383DE0FB7ABDC7DC775290D052E6D
12DFA68626D4D26FAA5829FC97ECFA82510F3080BEB1509E4644F12CBBD832CF
C6686F07D9B060ACBEEE34096A13F5F7050593DF5EBA3556D961FF197FC981E6
F86CEA874070EFAC6D2C749F2DFA553AB9997702A648528C4EF357385774575F
e=010001
d=
00A403C327477634346CA686B57949014B2E8AD2C862B2C7D748096A8B91F736
F275D6E8CD15906027314735644D95CD6763CEB49F56AC2F376E1CEE0EBF282D
F439906F34D86E085BD5656AD841F313D72D395EFE33CBFF29E4030B3D05A28F
B7F18EA27637B07957D32F2BDE8706227D04665EC91BAF8B1AC3EC9144AB7F21
The message to be signed is, of course,
M="abc"
that is, the 3 bytes in hex format,
M=616263
The message digest algorithm is SHA-1, so
H = Hash("abc") = A9993E364706816ABA3E25717850C26C9CD0D89D
The DigestInfo value for SHA-1 is
T=3021300906052B0E03021A05000414A9993E364706816ABA3E25717850C26C9C
D0D89D
The encoded message block, EB, after encoding but before signing is
0001FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00302130
0906052B0E03021A05000414A9993E364706816ABA3E25717850C26C9CD0D89D
After RSA signing, the output is
60AD5A78FB4A4030EC542C8974CD15F55384E836554CEDD9A322D5F4135C6267
A9D20970C54E6651070B0144D43844C899320DD8FA7819F7EBC6A7715287332E
C8675C136183B3F8A1F81EF969418267130A756FDBB2C71D9A667446E34E0EAD
9CF31BFB66F816F319D0B7E430A5F2891553986E003720261C7E9022C0D9F11F
The above hex data in C format.
Weaknesses in RSA
Small encryption exponent
If you use a small exponent like e=3 and send the same message to different recipients and just use the RSA algorithm without adding random padding to the message, then an eavesdropper could recover the plaintext.
For an example of this, see Cracking RSA on our page on the The Chinese Remainder Theorem.
Small encryption exponent and small message
If you use e=3 and just encrypt a small message m without padding where m3<n then your ciphertext c can easily be broken by simply computing its real cube root. For example, if we have the public key (n,e)=(25777,3) and just encrypt the small message m=10 then the ciphertext is c=1000. The secure properties of RSA encryption only work if me>n.
Using the same key for encryption and signing
Given that the underlying mathematics is the same for encryption and signing, only in reverse, if an attacker can convince a key holder to sign an unformatted encrypted message using the same key then she gets the original.
Using a common modulus for different users
Do not use the same modulus n with different (ei,di) pairs for different users in a group. Given his own pair (e1,d1), user 1 can factorize the common n into p and q and hence compute the private exponents di of all the other users.
For more details, see our page RSA: how to factorize N given d.
Acting as an oracle
There are techniques to recover the plaintext if a user just blindly returns the RSA transformation of the input. So don't do that.
Solutions
Don't use the same RSA key for encryption and signing.
Don't encrypt or sign a blind message.
If using PKCS#v1.5 encoding, use e=0x10001 for your public exponent.
Always format your input before encrypting or signing.
Always add fresh random padding - at least 8 bytes - to your message before encrypting.
When decrypting, check the format of the decrypted block. If it is not as expected, return an error message, not the decrypted string.
Similarly, when verifying a signature, if there is any error whatsoever, just respond with "Invalid Signature".
More Advanced Schemes
The underlying RSA operations
c=memodn,m′=cdmodn;s=mdmodn,s′=semodn
are always the same, but there are many variants of how these can be used inside an encryption or digital signature scheme. Here are some of them.
RSAES-OAEP
The OAEP encoding technique for encryption is described in PKCS#1 version 2 and in IEEE P136. It is more secure than the PKCS#1v1.5 encoding method described above, perhaps provably secure. The encoding technique involves a mask generation function (MGF) based on a hash function and there is no obvious structure in the encoded block, unlike the PKCS#1v1.5 encoding method. Despite being the recommended method for the last decade, OAEP is not used in practice as much as you'd expect. In fact, hardly at all. That said, if you have a choice in the matter, we recommend that you should use OAEP if you can.
RSASSA-PSS
The PSS encoding method is used to encode before creating a signature. The technique is described in PKCS#1v2.1 and is similar in design to the OAEP encoding used for encryption involving an MGF based on a hash function. However, there were active patents associated with this method until recently and so it is still not supported well. There are currently no known weaknesses with the PKCS#1v1.5 signature scheme.
X9.31 Signature Scheme
ANSI standard X9.31 [AX931] requires using strong primes derived in a way to avoid particular attacks that are probably no longer relevant. X9.31 uses a method of encoding the message digest specific to the hash algorithm. It expects a key with length an exact multiple of 256 bits. The same algorithm is also specified in P1363 [P1363] where it is called IFSP-RSA2. The scheme allows for the public exponent to be an even value, but we do not consider that case here; all our values of e are assumed to be odd. The message digest hash, H, is encapsulated to form a byte string as follows
EB = 06 || PS || 0xBA || H || 0x33 || 0xCC
where PS is a string of bytes all of value 0xBB of length such that |EB|=|n|, and 0x33 is the ISO/IEC 10118 part number† for SHA-1. The byte string, EB, is converted to an integer value, the message representative, f.
† ISO/IEC 10118 part numbers for other hash functions are: SHA-1=0x33, SHA-256=0x34, SHA-384=0x36, SHA-512=0x35, RIPEMD=0x31.
Algorithm: Forming an X9.31/RSA2 signature value from the message representative (for odd e).
INPUT: Signer's RSA private key, (n, d); integer, f, where 0≤f<n and f≡12(mod16).
OUTPUT: Signature, an integer s where 0≤s<n/2, i.e. a value at least one bit shorter than n.
t=fdmodn
s=min(t,n−t)
Output s.
The integer, s, is converted to a byte string of length |n| bytes.
Algorithm: Extracting the message representative from an X9.31/RSA2 signature value (for odd e).
INPUT: Signer's RSA public key, (n, e); signature, s.
OUTPUT: Message representative, f, such that f≡12(mod16), or "invalid signature".
If s is not in [0,(n−1)/2], output "invalid signature" and stop.
Compute t=semodn
If t≡12(mod16) then let f=t.
Else let f=n−t. If f≢12(mod16), output "invalid signature" and stop.
Output f.
The integer f is converted to a byte string of length |n| bytes and then parsed to confirm that all bytes match the required format
EB = 06 || PS || 0xBA || H || 0x33 || 0xCC
If not, output "invalid signature" and stop; otherwise output the extracted message digest hash, H.
ISO/IEC 9796
IOS/IEC 9796 is an old standard devised before there was a recognised message digest function like MD5 or SHA-1. It allows the entire message to be recovered. Unfortunately, it is considered broken for signing plain text messages, but is still OK for signing message digest values. It is used in the AUTACK scheme described in [EDIFACT].
The encapsulation mechanism weaves the input bytes into a format exactly one bit shorter than the RSA key. The signing mechanism is similar to that in ANSI X9.31 described above, but the message representative, f, is required to be f≡6(mod16), instead of modulo 12. In other words, make sure the last 4 bits are equal to 0x6 instead of 0xC.
RSA-KEM
The RSA-KEM Key Transport Algorithm encrypts a random integer with the recipient's public key, and then uses a symmetric key-wrapping scheme to encrypt the keying data. KEM stands for Key Encapsulation Mechanism. The general algorithm is as follows
Generate a random integer z between 0 and n−1.
Encrypt the integer z with the recipient's RSA public key: c=zemodn.
Derive a key-encrypting key KEK from the integer z.
Wrap the keying data using KEK to obtain wrapped keying data WK.
Output c and WK as the encrypted keying data.
This method has a higher security assurance than PKCS#1v1.5 because the input to the underlying RSA operation is random and independent of the message, and the key-encrypting key KEK is derived from it in a strong way. The downside is that you need to implement a key derivation method (of which there are many varieties) and a key wrapping algorithm. The encoding of the final data into the recommended ASN.1 format is messy, too. For more details, see the latest version of [CMSRSAKEM].
Ferguson-Schneier Encryption
In their book [FERG03], Niels Ferguson and Bruce Schneier suggest a much simpler method of encryption. They suggest using the same modulus n for both encryption and signatures but to use e=3 for signatures and e=5 for encryption. You need to make sure that the modulus n=pq satisfies both gcd(3,(p−1)(q−1))=1 and gcd(5,(p−1)(q−1))=1.
Their method uses RSA to encrypt a random integer and use a hash function to derive the actual content encryption key, thus removing any structural similarities between the actual CEK and the data encrypted by the RSA. They recommend using the function, Hash(x):=SHA256(SHA256(x)), for hashing data.
Algorithm: Ferguson-Schneier Encrypt Random Key with RSA.
INPUT: Recipient's RSA public key, (n, e).
OUTPUT: Content encryption key, CEK; RSA-encrypted CEK, c.
Compute the exact bit length of the RSA key, k=⌈log2(n+1)⌉.
Choose a random r in the interval [0,2k−1].
Compute the content encryption key by hashing r, CEK=Hash(r).
c=remodn.
Output CEK and c.
For a plaintext message, m, the transmission sent to the recipient is IntegerToString(c)||E_CEK(m), where ECEK(m) is the result of encrypting m with a symmetrical encryption algorithm using key, CEK. Given that the recipient knows the size of the RSA key and hence the exact number of bytes needed to encode c, it is a simple matter to parse the input received from the sender.
For example code of this algorithm in Visual Basic (both VB6 and VB.NET) using our CryptoSys PKI Toolkit, see Ferguson-Schneier RSA Encryption.
Notation and Conventions
We use the following notation and conventions in this page.
A || B denotes concatenation of byte (or bit) strings A and B.
|B| denotes the length of the byte (or bit) string B in bytes.
|n| denotes the length** of the non-negative integer n in bytes, |n|=⌈log2(n+1)⌉.
IntegerToString(i, n) is an n-byte encoding of the integer i with the most significant byte first (i.e. in "big-endian" order). So, for example,
IntegerToString(1,4)="00000001"
IntegerToString(7658,3)="001DEA"
StringToInteger(S) is the integer represented by the byte string S with the most significant byte first.
⌈x⌉ is the smallest integer, n, such that n≥x.
** Strictly speaking, this is the length of the shortest byte string that can encode the integer.
What is the difference between a bit string and an integer?
A string is a contiguous sequence of symbols, so the string "cat" is a sequence of the letters 'c', 'a' and 't'. A bit string is sequence of binary digits (bits) '0' and '1'. A byte string is similar except it consists of bytes, which are in turn sequences of 8 bits. So a bit string and a byte string are the same thing, except the latter is restricted to multiples of 8 bits. For example, using hexadecimal representation, the byte string "8002EA" is a sequence of 3 bytes, 0x80, 0x02 and 0xEA; and is equal to the bit string "100000000000001011101010".
A note on notation: To differentiate between byte strings and integers here, we show byte strings in hexadecimal representation inside quotes, so "8002EA" denotes the string of three consecutive bytes with hexadecimal values 80, 02 and EA, respectively. We use the "0x" prefix to denote integers, so 0x80 denotes the integer with hexadecimal value 80 (decimal 128), and 0x8002EA denotes the integer with hexadecimal value 8002EA (decimal 8389354). Everything here is in "big-endian" order, with the left-most bits the most significant.
A string can be split into sub-strings (e.g. "8002" and "EA") and two strings can be concatenated (joined up) to make another string. The order of symbols is important. The usual convention is to write byte strings with the most significant byte first ("big-endian" or network byte order).
An integer is a whole number that obeys the usual rules of integer arithmetic (1+1=2,5−2=3,3×2=6,6/3=2) and modular arithmetic (10+6≡4(mod12))). There is no limit in theory as to how large an integer can be: you can always add one to any integer. The integer 8,389,354 in decimal is the same as the number 0x8002EA in hexadecimal notation, but is not the same as the byte string "8002EA", even though it looks the same and may well be stored in your computer in the same form.
You can increment the integer 8389354 to get 8389354+1=8389355 (0x8002EB); but you cannot "increment" the byte string "8002EA". On the other hand, you can concatenate the byte strings "8002" and "EA" to make "8002EA"; but the integers 8389 and 354 do not add to make 8389354. The byte string "00008002EA" is strictly not the same as "8002EA" (the former has two extra bytes of value 0x00 at the start); but the integers 0x008002EA and 0x8002EA are equal (leading zeros do not count).
With RSA encryption, we typically want to encrypt a session key which is a bit string, but the RSA operation c=memodn is done with integers, so we need to represent the bit string as an integer first (in practice, we usually add some random bytes and other padding, but we'll ignore that for the time being). Once the RSA operation has been completed, we have another integer, c, but we need to store the result as a bit string, so we encode the integer as a bit (byte) string and pass that string onto our recipient.
Example: Suppose we wish to encrypt the 3-byte/24-bit key bit string "8002EA" using the RSA public key (n=25009997=0x017D9F4D, e=5)†. For simplicity in this insecure example, we will use the basic RSA algorithm with no padding.
The message block is the byte string "8002EA".
Compute the message representative
m = StringToInteger("8002EA") = 8389354
Encrypt with the RSA algorithm
c = 8389354^5 mod 25009997 = 2242555
Encode the result as a byte string
OB = IntegerToString(2242555, 4) = 002237FB
Note that the maximum length of the output block is 4 bytes, because the largest possible integer result is 0x017D9F4C (=n−1), which requires 4 bytes to store in encoded form.
† Thanks to "doctorjay" for pointing out that e=3 did not work for the earlier version of this example.
Implementation in C and VB
We show an example implementation of the RSA algorithm in C in our BigDigits library. It's not necessarily the most efficient way, and could be improved in its security, but it shows the maths involved. Look in the BigDigits Test Functions.
There is an example in VB6/VBA code at RSA and Diffie-Hellman in Visual Basic.
For a professional implementation, see our commercial CryptoSys PKI Toolkit which can be used with Visual Basic, VB6, VBA, VB2005+, C/C++ and C# applications. There are examples using the "raw" RSA functions to carry out RSA Encryption and RSA Signing.
