Различные вопросы о шифровании RSA

Question

В настоящее время я пишу свою собственную программу шифрования ASE/RSA на C++ для Unix. Я изучаю литературу уже около недели, и я начал обдумывать все это, но у меня все еще остаются некоторые насущные вопросы:

1) Исходя из моего понимания, ключ RSA в его наиболее простой форме представляет собой комбинацию произведения двух используемых простых чисел (R) и показателей степени. Для меня очевидно, что хранение ключа в таком виде в незашифрованном виде вообще лишит цели шифрования. Следовательно, в какой форме я могу хранить мои сгенерированные открытые и закрытые ключи? Попросите пользователя ввести пароль и выполните "простую" смену / замену отдельных цифр ключа таблицей ASCII? Или есть какой-то другой стандарт, с которым я не сталкивался? Кроме того, когда ключи генерируются, R и соответствующий показатель просто сохраняются последовательно? то есть ##primeproduct#### экспонент ##? В таком случае, как алгоритм дешифрования может разделить ключ на два отдельных значения?

2) Как бы я запрограммировал генерацию частного показателя, учитывая, что я решил использовать 65537 в качестве моего открытого показателя для всех шифрований? У меня есть уравнение P*Q = 1mod(M), где P и Q и показатели степени, а M - это результат функции Эйлера. Является ли это просто вопросом генерации случайных чисел и проверки их относительной первичности по отношению к общему показателю, пока вы не столкнетесь с платой грязи? Я знаю, что вы не можете просто начать с 1 и увеличивать до тех пор, пока не найдете такое число, поскольку любой может просто сделать то же самое и получить свой частный показатель самостоятельно.

3) При создании набора эквивалентности символов я понимаю, что числа, используемые в наборе, не могут быть меньше и относительно простыми относительно P*Q. Опять же, это вопрос проверки относительной простоты чисел к P*Q. Является ли скорость тестирования относительной простотой независимой от размера чисел, с которыми вы работаете? Или нужны специальные алгоритмы?

Заранее спасибо всем, кто нашел время, чтобы прочитать и ответить, ура!

Answer 1

Существует несколько стандартных форматов хранения / обмена ключами RSA, например RFC 3447. Что бы там ни было, большинство (многие так или иначе) используют кодировку ASN.1, которая сама по себе добавляет больше сложности, чем нравится большинству людей. Некоторые используют кодировку Base64, которую намного проще реализовать.

Что касается того, что составляет ключ, в его самой простой форме, вы правы; открытый ключ включает в себя модуль (обычно называется n) и показатель степени (обычно называется e).

Чтобы вычислить пару ключей, вы начинаете с двух больших простых чисел, обычно называемых p а также q, Вы вычисляете модуль n как p * q, Вы также вычисляете число (часто называемое r) это (p-1) * (q-1),

e затем более или менее случайно выбранный номер, который является простым относительно r, Предупреждение: ты не хочешь e чтобы быть действительно маленьким, хотя - log(e) >= log(n)/4 как минимум.

Затем вы вычислите d (закрытый ключ дешифрования) как число, удовлетворяющее соотношению:

d * e = 1 (mod r)

Вы обычно вычисляете это, используя алгоритм Евклида, хотя есть и другие варианты (см. Ниже). Опять не хочешь d быть очень маленьким, поэтому, если получится действительно небольшое число, вы, вероятно, захотите попробовать другое значение для e и вычислить новый d чтобы соответствовать.

Есть еще один способ вычислить ваш e а также d, Вы можете начать с нахождения некоторого числа K, которое совпадает с 1 mod r, а затем разложить его. Соедините главные факторы, чтобы получить два фактора примерно одинакового размера, и используйте их как e а также d,

Насколько злоумышленник вычисляет ваш d идет: тебе нужно r вычислить это, и зная r зависит от знания p а также q, Именно поэтому / где / как факторинг вступает в ломку RSA. Если вы учитываете n тогда ты знаешь p а также q, Из них вы можете найти r, и из r Вы можете вычислить d это соответствует известному e,

Итак, давайте проработаем математику, чтобы создать пару ключей. Мы собираемся использовать простые числа, которые слишком малы, чтобы быть эффективными, но их должно быть достаточно, чтобы продемонстрировать соответствующие идеи.

Итак, начнем с выбора ap и q (конечно, оба должны быть простыми числами):

p = 9999991
q = 11999989

Из тех, которые мы вычисляем n а также r:

n = 119999782000099
r = 119999760000120

Далее нам нужно либо выбрать e или вычислить K, то фактор это, чтобы получить e а также d, На данный момент, мы пойдем с вашим предложением е =65537 (так как 65537 является простым, единственная возможность для этого и r не относительные простые числа будут, если r был точным кратным 65537, что, как мы можем проверить, не так легко).

Исходя из этого, нам нужно вычислить наши d, Мы можем сделать это довольно легко (хотя и не обязательно очень быстро), используя "расширенную" версию алгоритма Евклида, (как вы упомянули) метод Эйлера, метод Гаусса или любой из ряда других.

На данный момент я вычислю это, используя метод Гаусса:

template <class num>
num gcd(num a, num b) {
    num r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

template <class num>
num find_inverse(num a, num p) {
    num g, z;

    if (gcd(a, p) > 1) return 0;

    z = 1;

    while (a > 1) {
        z += p;
        if ((g=gcd(a, z))> 1) {
            a /= g;
            z /= g;
        }
    }
    return z;
}

Результат, который мы получаем:

d = 38110914516113

Затем мы можем подключить их к реализации RSA и использовать их для шифрования и дешифрования сообщения.

Итак, давайте зашифруем "Совершенно секретное сообщение!". С использованием e а также n учитывая выше, что шифрует до:

74603288122996
49544151279887
83011912841578
96347106356362
20256165166509
66272049143842
49544151279887
22863535059597
83011912841578
49544151279887
96446347654908
20256165166509
87232607087245
49544151279887
68304272579690
68304272579690
87665372487589
26633960965444
49544151279887
15733234551614

И, используя d учитывая выше, это расшифровывает обратно к оригиналу. Код для шифрования / дешифрования (с использованием жестко закодированных ключей и модуля) выглядит следующим образом:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <functional>

typedef unsigned long long num;

const num e = 65537;
const num d = 38110914516113;
const num n = 119999782000099;

template <class T>
T mul_mod(T a, T b, T m) { 
    if (m == 0) return a * b;

    T r = T();

    while (a > 0) {
        if (a & 1)
            if ((r += b) > m) r %= m;
        a >>= 1;
        if ((b <<= 1) > m) b %= m;
    }
    return r;
}

template <class T>
T pow_mod(T a, T n, T m) {
    T r = 1;

    while (n > 0) {
        if (n & 1)
            r = mul_mod(r, a, m);
        a = mul_mod(a, a, m);
        n >>= 1;
    }
    return r;
}

struct crypt : std::binary_function<num, num, num> {
    num operator()(num input, num key) const {
        return pow_mod(input, key, n);
    }
};

int main() {
    std::string msg = "Very Secret Message!";
    std::vector<num> encrypted;

    std::transform(msg.begin(), msg.end(),  
        std::back_inserter(encrypted),
        std::bind2nd(crypt(), e));

    std::copy(encrypted.begin(), encrypted.end(), std::ostream_iterator<num>(std::cout, "\n"));

    std::cout << "\n";

    std::transform(encrypted.begin(), encrypted.end(), 
        std::ostream_iterator<char>(std::cout, ""), 
        std::bind2nd(crypt(), d));
    std::cout << "\n";

    return 0;
}

Чтобы иметь хоть надежду на безопасность, вам нужно использовать гораздо больший модуль - хотя бы сотни битов (и, возможно, тысячу или более для параноика). Вы можете сделать это с помощью обычной целочисленной библиотеки произвольной точности или подпрограмм, написанных специально для данной задачи. RSA по своей природе довольно медленный, поэтому в свое время большинство реализаций использовали для выполнения работы код с большой оптимизацией. В настоящее время аппаратное обеспечение достаточно быстрое, так что вы, вероятно, довольно легко справитесь с довольно средне-целочисленной библиотекой (особенно потому, что при реальном использовании вы хотите использовать только RSA для шифрования / дешифрования ключа для симметричного алгоритма, а не для шифрования необработанные данные).