1973年，在英國政府通訊總部工作的數學家克利福德·柯克斯（Clifford Cocks）在一個內部檔案中提出了一個相應的算法，但他的發現被列入機密，一直到1997年才被發表。
RSA算法的可靠性基於分解極大的整數是很困難的。假如有人找到一種很快的分解因子的算法的話，那么用RSA加密的信息的可靠性就肯定會極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的RSA鑰匙才可能被強力方式解破。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。
1983年麻省理工學院在美國為RSA算法申請了專利。這個專利2000年9月21日失效。由於該算法在申請專利前就已經被發表了，在世界上大多數其它地區這個專利權不被承認。
操作
公鑰和私鑰的產生
假設Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個密鑰：
隨意選擇兩個大的質數p和q，p不等於q，計算N=pq。
根據歐拉函式,不大於N且與N互質的整數個數為(p-1)(q-1)
選擇一個整數e與(p-1)(q-1)互質,並且e小於(p-1)(q-1)
用以下這個公式計算d：d× e ≡ 1 (mod (p-1)(q-1))
將p和q的記錄銷毀。
e是公鑰，d是私鑰。d是秘密的，而N是公眾都知道的。Alice將她的公鑰傳給Bob，而將她的私鑰藏起來。
加密訊息
假設Bob想給Alice送一個訊息m，他知道Alice產生的N和e。他使用起先與Alice約好的格式將m轉換為一個小於N的整數n，比如他可以將每一個字轉換為這個字的Unicode碼，然後將這些數字連在一起組成一個數字。假如他的信息非常長的話，他可以將這個信息分為幾段，然後將每一段轉換為n。用下面這個公式他可以將n加密為c：
計算c並不複雜。Bob算出c後就可以將它傳遞給Alice。
解密訊息
Alice得到Bob的訊息c後就可以利用她的密鑰d來解碼。她可以用以下這個公式來將c轉換為n：
得到n後，她可以將原來的信息m重新復原。
解碼的原理是
以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。費馬小定理證明
和
和
這說明（因為p和q是不同的質數）
簽名訊息
RSA也可以用來為一個訊息署名。假如甲想給乙傳遞一個署名的訊息的話，那么她可以為她的訊息計算一個散列值，然後用她的密鑰加密這個散列值並將這個“署名”加在訊息的後面。這個訊息只有用她的公鑰才能被解密。乙獲得這個訊息後可以用甲的公鑰解密這個散列值，然後將這個數據與他自己為這個訊息計算的散列值相比較。假如兩者相符的話，那么他就可以知道發信人持有甲的密鑰，以及這個訊息在傳播路徑上沒有被篡改過。
安全
假設偷聽者乙獲得了甲的公鑰N和e以及丙的加密訊息c，但她無法直接獲得甲的密鑰d。要獲得d，最簡單的方法是從c算出n，然後將N分解為p和q，這樣她可以計算(p-1)(q-1)並從而由e推算出d。至今為止還沒有人找到一個多項式時間的計算方法來分解一個大的整數的因子，但至今為止也還沒有人能夠證明這種算法不存在（見因式分解）。
至今為止也沒有人能夠證明對N進行分解因式是唯一的從c導出n的方法，但今天還沒有找到比它更簡單的方法。（至少沒有公開的方法。）
因此今天一般認為只要N足夠大，那么黑客就沒有辦法了。
假如N的長度小於或等於256位，那么用一台個人電腦在幾個小時內就可以分解它的因子了。1999年，數百台電腦合作分解了一個512位長的N。今天對N的要求是它至少要1024位長。
1994年彼得·秀爾（Peter Shor）證明一台量子計算機可以在多項式時間內進行因式分解。假如量子計算機有朝一日可以成為一種可行的技術的話，那么秀爾的算法可以淘汰RSA和相關的算法。
假如有人能夠找到一種有效的分解因式的算法的話，或者假如量子計算機可行的話，那么在解密和製造更長的鑰匙之間就會展開一場競爭。但從原理上來說RSA在這種情況下是不可靠的。
實現細節
用Java實現RSA加密
package net.52java.utils.security;
import javax.crypto.Cipher;
import java.security.*;
import java.security.spec.RSAPublicKeySpec;
import java.security.spec.RSAPrivateKeySpec;
import java.security.spec.InvalidKeySpecException;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.io.*;
import java.math.BigInteger;
/**
* RSA 工具類。提供加密，解密，生成密鑰對等方法。
* 需要到http://www.bouncycastle.org下載bcprov-jdk14-123.jar。
* @author xiaoyusong
* mail: [email protected]
* msn:[email protected]
* @since 2004-5-20
*
*/
public class RSA{
/**
* 生成密鑰對
* @return KeyPair
* @throws Exception
*/
public static KeyPair generateKeyPair() throws Exception {
try {
KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance("RSA",
new org.bouncycastle.jce.provider.BouncyCastleProvider());
final int KEY_SIZE = 1024;//沒什麼好說的了，這個值關係到塊加密的大小，可以更改，但是不要太大，否則效率會低
keyPairGen.initialize(KEY_SIZE, new SecureRandom());
KeyPair keyPair = keyPairGen.genKeyPair();
return keyPair;
} catch (Exception e) {
throw new Exception(e.getMessage());
}
}
/**
* 生成公鑰
* @param modulus
* @param publicExponent
* @return RSAPublicKey
* @throws Exception
*/
public static RSAPublicKey generateRSAPublicKey(byte[] modulus, byte[] publicExponent) throws Exception {
KeyFactory keyFac = null;
try {
keyFac = KeyFactory.getInstance("RSA", new org.bouncycastle.jce.provider.BouncyCastleProvider());
} catch (NoSuchAlgorithmException ex) {
throw new Exception(ex.getMessage());
}
RSAPublicKeySpec pubKeySpec = new RSAPublicKeySpec(new BigInteger(modulus), new BigInteger(publicExponent));
try {
return (RSAPublicKey) keyFac.generatePublic(pubKeySpec);
} catch (InvalidKeySpecException ex) {
throw new Exception(ex.getMessage());
}
}
/**
* 生成私鑰
* @param modulus
* @param privateExponent
* @return RSAPrivateKey
* @throws Exception
*/
public static RSAPrivateKey generateRSAPrivateKey(byte[] modulus, byte[] privateExponent) throws Exception {
KeyFactory keyFac = null;
try {
keyFac = KeyFactory.getInstance("RSA", new org.bouncycastle.jce.provider.BouncyCastleProvider());
} catch (NoSuchAlgorithmException ex) {
throw new Exception(ex.getMessage());
}
RSAPrivateKeySpec priKeySpec = new RSAPrivateKeySpec(new BigInteger(modulus), new BigInteger(privateExponent));
try {
return (RSAPrivateKey) keyFac.generatePrivate(priKeySpec);
} catch (InvalidKeySpecException ex) {
throw new Exception(ex.getMessage());
}
}
/**
* 加密
* @param key 加密的密鑰
* @param data 待加密的明文數據
* @return 加密後的數據
* @throws Exception
*/
public static byte[] Encrypt(Key key, byte[] data) throws Exception {
try {
Cipher cipher = Cipher.getInstance("RSA", new org.bouncycastle.jce.provider.BouncyCastleProvider());
cipher.init(Cipher.ENCRYPT_MODE, key);
int blockSize = cipher.getBlockSize();//獲得加密塊大小，如：加密前數據為128個byte，而key_size=1024 加密塊大小為127 byte,加密後為128個byte;因此共有2個加密塊，第一個127 byte第二個為1個byte
int outputSize = cipher.getOutputSize(data.length);//獲得加密塊加密後塊大小
int leavedSize = data.length % blockSize;
int blocksSize = leavedSize != 0 ? data.length / blockSize + 1 : data.length / blockSize;
byte[] raw = new byte[outputSize * blocksSize];
int i = 0;
while (data.length - i * blockSize > 0) {
if (data.length - i * blockSize > blockSize)
cipher.doFinal(data, i * blockSize, blockSize, raw, i * outputSize);
else
cipher.doFinal(data, i * blockSize, data.length - i * blockSize, raw, i * outputSize);
//這裡面doUpdate方法不可用，查看原始碼後發現每次doUpdate後並沒有什麼實際動作除了把byte[]放到ByteArrayOutputStream中，而最後doFinal的時候才將所有的byte[]進行加密，可是到了此時加密塊大小很可能已經超出了OutputSize所以只好用dofinal方法。
i++;
}
return raw;
} catch (Exception e) {
throw new Exception(e.getMessage());
}
}
/**
* 解密
* @param key 解密的密鑰
* @param raw 已經加密的數據
* @return 解密後的明文
* @throws Exception
*/
public static byte[] Decrypt(Key key, byte[] raw) throws Exception {
try {
Cipher cipher = Cipher.getInstance("RSA", new org.bouncycastle.jce.provider.BouncyCastleProvider());
cipher.init(cipher.DECRYPT_MODE, key);
int blockSize = cipher.getBlockSize();
ByteArrayOutputStream bout = new ByteArrayOutputStream(64);
int j = 0;
while (raw.length - j * blockSize > 0) {
bout.write(cipher.doFinal(raw, j * blockSize, blockSize));
j++;
}
return bout.toByteArray();
} catch (Exception e) {
throw new Exception(e.getMessage());
}
}
/**
*
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
File file = new File("c:/test.html");
FileInputStream in = new FileInputStream(file);
ByteArrayOutputStream bout = new ByteArrayOutputStream();
byte[] tmpbuf = new byte[1024];
int count = 0;
while ((count = in.read(tmpbuf)) != -1) {
bout.write(tmpbuf, 0, count);
tmpbuf = new byte[1024];
}
in.close();
byte[] orgData = bout.toByteArray();
KeyPair keyPair = RSA.generateKeyPair();
RSAPublicKey pubKey = (RSAPublicKey) keyPair.getPublic();
RSAPrivateKey priKey = (RSAPrivateKey) keyPair.getPrivate();
byte[] pubModBytes = pubKey.getModulus().toByteArray();
byte[] pubPubExpBytes = pubKey.getPublicExponent().toByteArray();
byte[] priModBytes = priKey.getModulus().toByteArray();
byte[] priPriExpBytes = priKey.getPrivateExponent().toByteArray();
RSAPublicKey recoveryPubKey = RSA.generateRSAPublicKey(pubModBytes,pubPubExpBytes);
RSAPrivateKey recoveryPriKey = RSA.generateRSAPrivateKey(priModBytes,priPriExpBytes);
byte[] raw = RSA.encrypt(priKey, orgData);
file = new File("c:/encrypt_result.dat");
OutputStream out = new FileOutputStream(file);
out.write(raw);
out.close();
byte[] data = RSA.decrypt(recoveryPubKey, raw);
file = new File("c:/decrypt_result.html");
out = new FileOutputStream(file);
out.write(data);
out.flush();
out.close();
}
}
密鑰生成
首先要使用機率算法來驗證隨機產生的大的整數是否質數，這樣的算法比較快而且可以消除掉大多數非質數。假如有一個數通過了這個測試的話，那么要使用一個精確的測試來保證它的確是一個質數。
除此之外這樣找到的p和q還要滿足一定的要求，首先它們不能太靠近，此外p-1或q-1的因子不能太小，否則的話N也可以被很快地分解。
此外尋找質數的算法不能給攻擊者任何信息，這些質數是怎樣找到的，尤其產生隨機數的軟體必須非常好。要求是隨機和不可預測。這兩個要求並不相同。一個隨機過程可能可以產生一個不相關的數的系列，但假如有人能夠預測出（或部分地預測出）這個系列的話，那么它就已經不可靠了。比如有一些非常好的隨機數算法，但它們都已經被發表，因此它們不能被使用，因為假如一個攻擊者可以猜出p和q一半的位的話，那么他們就已經可以輕而易舉地推算出另一半。
此外密鑰d必須足夠大，1990年有人證明假如p大於q而小於2q（這是一個很經常的情況）而d < N1/4/3，那么從N and e可以很有效地推算出d。此外e = 2永遠不應該被使用。
速度
比起DES和其它對稱算法來RSA要慢得多。實際上巴哥一般使用一種對稱算法來加密他的信息，然後用RSA來加密他的比較短的對稱密碼，然後將用RSA加密的對稱密碼和用對稱算法加密的訊息送給阿黃。
這樣一來對隨機數的要求就更高了，尤其對產生對稱密碼的要求非常高，因為否則的話可以越過RSA來直接攻擊對稱密碼。
密鑰分配
和其它加密過程一樣，對RSA來說分配公鑰的過程是非常重要的。分配公鑰的過程必須能夠抵擋一個從中取代的攻擊。假設娥妹交給巴哥一個公鑰，並使巴哥相信這是阿黃的公鑰，並且她可以截下阿黃和巴哥之間的信息傳遞，那么她可以將她自己的公鑰傳給巴哥，巴哥以為這是阿黃的公鑰。可以將所有巴哥傳遞給阿黃的訊息截下來，將這個訊息用她自己的密鑰解密，讀這個訊息，然後將這個訊息再用阿黃的公鑰加密後傳給阿黃。理論上阿黃和巴哥都不會發現娥妹在偷聽他們的訊息。今天人們一般用數字認證來防止這樣的攻擊。
時間攻擊
1995年有人提出了一種非常意想不到的攻擊方式：假如娥妹對阿黃的硬體有充分的了解，而且知道它對一些特定的訊息加密時所需要的時間的話，那么她可以很快地推導出d。這種攻擊方式之所以會成立，主要是因為在進行加密時所進行的模指數運算是一個位元一個位元進行的，而位元為1所花的運算比位元為0的運算要多很多，因此若能得到多組訊息與其加密時間，就會有機會可以反推出私鑰的內容。
操作
典型密鑰長度
1997年後開發的系統，用戶應使用1024位密鑰，證書認證機構套用2048位或以上。
已公開的或已知的攻擊方法
針對RSA最流行的攻擊一般是基於大數因數分解。1999年，RSA-155(512 bits)被成功分解，花了五個月時間（約8000 MIPS 年)和224 CPU hours 在一台有3.2G中央記憶體的Cray C916計算機上完成 。
2002年，RSA-158也被成功因數分解。
