3. Описание алгоритма:
Формирование ключей
Выбирается два больших простых числа
и
Вычисляется
Выбирается произвольное число
,
взаимно простое с
Составляется и решается в целых числах Диофантово уравнение
относительно
Пара чисел
- открытый ключ
Пара чисел
- закрытый ключ
Шифрование
Сообщение разбивается на блоки размером
бит. Такой блок может рассматриваться
как
-битное
целое число. Обозначим такой блок
Для каждого блока вычисляется значение
,
которое является шифрованным блоком
сообщения. Размер шифрованного блока
равен размеру блока исходного сообщения
Дешифрование
Для каждого блока шифрованного сообщения
вычисляется значение
,
которое является дешифрованным блоком
сообщения
4. Реализация алгоритма:
RSACrypt:
import java.math.BigInteger;
import java.util.Date;
import java.util.Random;
public class RSACrypt {
private BigInteger p;
private BigInteger q;
/**
* Common key part
*/
private BigInteger m;
private BigInteger mBackup = BigInteger.ZERO;
/**
* Public key
*/
private BigInteger e;
private BigInteger eBackup = BigInteger.ZERO;
/**
* Private key
*/
private BigInteger d;
private BigInteger dBackup = BigInteger.ZERO;
/**
* Length of the key in bits
*/
private int keyLength = 512;
/**
* Generate keys
*/
private void calculateParams() {
p = BigInteger.probablePrime(keyLength/2, new Random(new Date().getTime()));
q = p.nextProbablePrime();
m = p.multiply(q);
BigInteger phi = p.subtract(BigInteger.ONE).
multiply(q.subtract(BigInteger.ONE));
int startLen = keyLength*3/4;
e = BigInteger.probablePrime(startLen, new Random(new Date().getTime()));
while (phi.gcd(e).compareTo(BigInteger.ONE) != 0)
e = BigInteger.probablePrime(++startLen, new Random(new Date().getTime()));
BigInteger[] curDivRem = new BigInteger[2];
//BigInteger Pim2 = BigInteger.ZERO;
//BigInteger Pim1 = BigInteger.ONE;
BigInteger Qim2 = BigInteger.ONE;
BigInteger Qim1 = BigInteger.ZERO;
BigInteger curDiv = phi;
BigInteger curVal = e;
curDivRem = curVal.divideAndRemainder(curDiv);
int k = 0;
while (curDivRem[1].compareTo(BigInteger.ZERO) != 0) {
BigInteger Q = curDivRem[0].multiply(Qim1).add(Qim2);
Qim2 = Qim1;
Qim1 = Q;
//BigInteger P = curDivRem[0].multiply(Pim1).add(Pim2);
//Pim2 = Pim1;
//Pim1 = P;
curVal = curDiv;
curDiv = curDivRem[1];
curDivRem = curVal.divideAndRemainder(curDiv);
k++;
}
d = ((k-1)%2==1) ? Qim1.negate() : Qim1;
}
public RSACrypt() {
calculateParams();
}
/**
* Generate new keys
*/
public void regenerateKeys() {
calculateParams();
}
/**
* Set private key to the given value. No checks are perfomed
* @param key BigInteger value to set private key to
*/
public void setPrivateKey(BigInteger key) {
if (dBackup.compareTo(BigInteger.ZERO) == 0) dBackup = d;
d = key;
}
public void setPublicKey(BigInteger key) {
if (eBackup.compareTo(BigInteger.ZERO) == 0) eBackup = e;
e = key;
}
public void setCommonKeyPart(BigInteger value) {
if (mBackup.compareTo(BigInteger.ZERO) == 0) mBackup = m;
m = value;
}
public void restorePrivateKey() {
if (dBackup.compareTo(BigInteger.ZERO) != 0) d = dBackup;
}
public void restorePublicKey() {
if (eBackup.compareTo(BigInteger.ZERO) != 0) e = eBackup;
}
public void restoreCommonKeyPart() {
if (mBackup.compareTo(BigInteger.ZERO) != 0) m = mBackup;
}
/**
* Set key length to the given value. Setting new length of the key causes
* private and public keys regeneration
* @param length int Length in bits of the key to set (must be greater than
* or equal to 16)
* @return int 0 if length < 16, 1 - otherwise
*/
public int setKeyLength(int length) {
if (length < 16) return 0;
keyLength = length;
calculateParams();
return 1;
}
public BigInteger getP() {
return p;
}
public BigInteger getQ() {
return q;
}
public BigInteger getCommonKeyPart() {
return m;
}
public BigInteger getPublicKey() {
return e;
}
public BigInteger getPrivateKey() {
return d;
}
public int getKeyLength() {
return keyLength;
}
/**
* Encrypt message using RSA public key
* @param text byte[] Array of message bytes to encrypt. Length of array should be
* getKeyLength()/8. If length is less then array will be expanded with zeros.
* If length is greater then array will be trimmed
* @return byte[] Array of encrypted message bytes
*/
public byte[] Encrypt(byte[] text) {
int length = keyLength/8;
byte[] temp = new byte[length];
for (int i=0; i<text.length; i++) temp[i] = text[i];
BigInteger x = new BigInteger(temp);
temp = x.modPow(e, m).toByteArray();
byte[] res = new byte[length];
if (temp.length > length)
for (int i=1; i<=length; i++) res[length-i] = temp[temp.length-i];
else
for (int i=1; i<=temp.length; i++) res[length-i] = temp[temp.length-i];
return res;
}
/**
* Decrypt message using RSA private key
* @param cryptText byte[] Encrypted message to decrypt. Length of array
* should be getKeyLength()/8. If length is not equal to getKeyLength()/8
* then result is undefined
* @return byte[] Array of decrypted message bytes
*/
public byte[] Decrypt(byte[] cryptText) {
BigInteger y = new BigInteger(cryptText);
return y.modPow(d, m).toByteArray();
}
/**
* Converts sequence of bytes to its string representation in hexadecimal
* format without sign extension
* @param bytes byte[] sequence of bytes to convert
* @return String hexadecimal representation of byte sequence
*/
public static String BytesToString(byte[] bytes) {
StringBuffer res = new StringBuffer(bytes.length*2);
String temp = new String();
for (int i=0; i<bytes.length; i++) {
temp = Integer.toHexString(bytes[i]);
if (temp.length() <= 2) {
if (temp.length() == 1) res.append('0');
res.append(temp);
}
else res.append(temp.substring(6));
}
return res.toString();
}
}