Здравствуйте, читатели, сегодня я собираюсь сделать краткий обзор шифрования RSA. RSA — это криптосистема с открытым ключом, и ее пример использования в учебнике выглядит примерно так:
Предположим, у вас есть два человека Алиса и Боб. Алиса хочет отправить Бобу сообщение. Теперь это довольно тривиальная задача, однако предположим, что Алиса хочет отправить Бобу защищенное сообщение, которое может прочитать только он.
Теперь несколько фактов о RSA, прежде чем я напишу немного кода. RSA опирается на модульную арифметику и трудность разложения больших чисел на множители до их простых корней. Первый настолько полезен, потому что его операции обратимы, а последний - в целях безопасности. Полагаясь на систему, которая является обратимой, мы можем «отменять» определенные операции… это будет полезно для расшифровки.
Немного работы по дому, прежде чем Алиса сможет отправить Бобу сообщение. Боб должен определиться с некоторыми переменными:
PRIVATE p: very large prime PRIVATE q: very large prime PUBLIC n: p * q PRIVATE a: φ(n)= (Euler's Totient function) = (p-1)(q-1) PUBLIC e: 2 < e < a & e coprime to a to ensure an inverse exists PRIVATE d: e*d ≡ 1 mod (a) <------ d is multiplicative inverse to e
Из этих 6 переменных Боб определит; p, q и e, а затем использовать функции для вычисления переменных; a, n и d. Как только Боб получит все свои переменные, он сможет передать Алисе свой открытый ключ (n,e) И ТОЛЬКО СВОЮ ПУБЛИЧНУЮ ИНФОРМАЦИЮ. Передача любой непубличной переменной приведет к нарушению безопасности системы.
(n is getting tagged on for js BigInt functionality) p = 139969n (small primes used for simplicity and readability) q = 126247697n n = p*q = 17670763901393n a = φ(n) = (p-1)(q-1)= 17670637513728n e = 30029n (coprime to a) d = 6731895606149n (multiplicative inverse to e mod a)
Теперь Боб отправляет Алисе свой открытый ключ (n,e) = (17670763901393n, 30029n) и держит все остальное в секрете и в безопасности. Итак, теперь, когда у Алисы есть открытый ключ, что она с ним делает? Ну, она делает с ним «RSA»…
Alice's message = m public key = (n,e) (m^ᵉ)mod(n)≡ c c is now encrypted using RSA
Алиса теперь может отправить безопасное сообщение Бобу, используя этот открытый ключ и RSA, верно? Ну нет... в настоящее время Алиса может отправлять номера только Бобу. Итак, как нам отправить настоящее сообщение Бобу? Итак, мы преобразуем нашу строку сообщения в число. Затем выполните наш алгоритм для нашего сообщения, которое является числом (небольшое предостережение, числовое значение сообщения должно быть меньше n, иначе модульная арифметика вызовет двусмысленность)
(Luckily JS has nice functionality for turning strings into numbers)
console.log('hello'.charCodeAt(0))
returns 104
В приведенном выше фрагменте используется встроенный метод String charCodeAt(), который возвращает значение Unicode от 0 до 255; все еще не совсем там, поскольку шифрование побуквенно крайне неэффективно, и нам пришлось бы предварительно формировать 5 шифровок только для того, чтобы зашифровать привет. (это также приводит к огромным проблемам с безопасностью, если каждая буква кодируется отдельно, поскольку можно использовать частотный анализ). Вместо этого мы будем использовать charCodeAt для создания массива значений utf8Byte, а затем использовать
Итак, мы создадим массив юникода, а затем возьмем байты и поместим их в одно число…
Node.js имеет хорошую библиотеку для преобразования строк в массив Unicode.
const hiBuf = Buffer.from('hello');
console.log(hiBuf[0])
//logs: 104
console.log(hiBuf)
//logs:
//Uint8Array(5) [104, 101, 108, 108, 111, buffer: ArrayBuffer(5), //byteLength: 5, byteOffset: 0, length: 5, //Symbol(Symbol.toStringTag): 'Uint8Array']
так что теперь мы берем этот массив unit8 и превращаем его в одно целое число
//taken from stackoverflow
pass in an array of bytes that is the message 'hello' in byte form
const byteArrayToLong = (/*byte[]*/byteArray) => {
var value = 0;
for ( var i = byteArray.length - 1; i >= 0; i--) {
value = (value * 256) + byteArray[i];
}
return value;
};
console.log(byteArrayToLong(hiBuf)
//here we pass in the array from above
//returns a single number 478560413032
Теперь у Алисы есть единственный номер, который она может зашифровать и отправить БОБУ УРА!
Как это выглядит, как вы говорите?
public key (n,e) =(17670763901393n, 30029n) Alice's message = 478560413032 (m^ᵉ)mod(n)≡ c 478560413032n^(30029n)mod(17670763901393n) = c c = 1246933000192n c is the encrypted message
Теперь Алиса отправляет Бобу c, и теперь Боб может расшифровать c, чтобы получить исходное сообщение. Мы делаем это, взяв по модулю (c ^ d), где d — наша модульная инверсия:
c = 1246933000192n using the mod inverse of e (d) ***** e*d ≡ 1 mod a ****** c ≡(m^ᵉ)mod(n) (c^d)≡(m^(e*d))mod(n)≡ (m^1)mod(n)≡ m m = original number that Alice encrypted
Теперь у Боба есть исходный номер, зашифрованный Алисой, и он может выполнить те же действия, что и Алиса, чтобы преобразовать исходное сообщение в число:
m = 478560413032 turning this number into byte array let array = longToByteArray(m) //array = ([104, 101, 108, 108, 111, 0, 0, 0]) let word = utf8ByteArrayToString(array) //word = hello
Боб получил привет именно то, что мы хотели, несмотря на то, что он получил только номер 1246933000192n.
источники:
общее чтение rsa:
Буфер node.js:
отрезано, чтобы преобразовать массив байтов в целое число и обратно
(учитывая больше времени, использование более обновленного подхода будет быстрее)
возведение в степень:
https://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method
