Асимметричное шифрование. RSA это очень просто.

Раньше я уже искал либы для микроконтроллера с реализацией Асимметричное шифрования, но ничего путевого не нашел. Я делал главную ошибку. Я искал в рунете! Я постоянно натыкался на посты где трындели, что это очень сложно и микроконтроллер не потянет. Так вот, это П***шь и его потянет даже avr.

И бла бла бла. В общем первые же поиски на англоязычных сайтах увенчались успехом.


Для начала я наткнулся на годную статейку. В ней демонстрируется работа RSA-32. Во первых удивило, что это очень просто и главное работает. Но не демонстрируется генерация ключей.

Продолжил поиски и нашел годный материал на вики. Также следует посмотреть русскоязычную вики. Там некоторые главы очень кошерные.

Еще немного и нашел вин. Это статья Z0MBiE. В ней есть все! Можно даже ограничится чтением его статьи. Разжевано и показано абсолютно все. Его статья обязательна к прочтению.

Требуется


Организовать защищенный радиоканал между двумя трансиверами. Для организации защищенного канала будут использоваться алгоритмы RSA-32 и AES-128.

RSA-32 софтварный.
AES-128 хардварный.

Утечка данных не приведет к потере денег.

Также, учитывая ненадежность 32х битного ключа, будут предприняты другие меры защиты. Такие как:
  • постоянное изменение настроек трансивера;
  • ограниченное время жизни канала;
  • использованы статические ключи шифрования.Их можно получить только из прошивки или исходного кода;
  • открытые ключи рекурсивны. Почти тоже самое, что и 3DES;
  • распознание свой/чужой.


Надежность RSA


На сегодняшний день RSA-1024 еще считается надежным, хотя и доживает последние дни. Уже начинают переходить на RSA-2048. Подразумевается не алгоритм а длина ключа. Также имеется ввиду факт взлома а не затраченное время на взлом. Предшественника RSA-1024 кластер ломал чуть более 4х лет.

Статьи британских ученых не учитываются:
— «Отрезание пальцев у админа привело к раскрытию RSA-1024»
— «Руткит взломал RSA-1024 путем передачи приватного ключа по сети!»
— «Мы вь**бали молотком по процессору и получили кусок приватного ключа!»
— и т.п.

RSA-32 уже давно можно взломать менее чем за сутки.

Надежность можно повысить используя:
-крипто процессор. Скорей всего вы его куй достанете. Продажа только по лицензии.
-fpga. Но помимо реализации алгоритма шифрования еще очень важны генераторы случайных и простых чисел.
-RSA акселератор. Некоторые ARM могут им похвастаться. Но в них используются только 128/256 битные ключи. Также генератор простых чисел только софтварный.
-использовать отдельный микроконтроллер. Мощный микроконтроллер запросто потянет 1024/2048 битные ключи. Использование таких ключей в обязательном порядке сожрет все процессорное время, ведь речь идет о миллионах процессорных тактов.

Кстати есть реализация 1024 и 2048 битных ключей для AVR! Проект сделан just for fun. Демонстрируется лишь возможность шифровки/расшифровки. В реальных проектах использовать невозможно.

На ARM можно использовать 64 и даже 128 битные ключи (имеется ввиду, что этот микроконтроллер занимается не только шифрованием). Следует учитывать, что есть нелинейная зависимость между временем шивфрования/дешифрования и длинной ключа. Также есть зависимость между размером зашифрованного сообщения и длинной ключа.

Немного реализации


Это не HOWTO и не либа а пример. Код лучше затачивать под конкретный камень. Даже RSA-32 запросто сожрет пару 100к процессорных тактов на 8ми битке.

У иностранца я забрал себе следующий код
huge_t modexp(huge_t a, huge_t b, huge_t n) 
{
  huge_t y=1;

  /*  Compute pow(a, b) % n using the binary square and multiply method. */
  while (b != 0) 
  {
    /*  For each 1 in b, accumulate y. */
    if (b & 1)
    {
      y = (y * a) % n;
    }
    
    /* Square a for each bit in b. */
    a = (a * a) % n;
    
    /*  Prepare for the next bit in b. */
    b = b >> 1;
  }

  return y;
}


void rsaEncrypt(huge_t plaintext, huge_t *ciphertext, rsaPubKey_t pubkey) 
{
  *ciphertext = modexp(plaintext, pubkey.e, pubkey.n);
}

void rsaDecrypt(huge_t ciphertext, huge_t *plaintext, rsaPriKey_t prikey) 
{
  *plaintext = modexp(ciphertext, prikey.d, prikey.n);
}


Он реально работает.В нем используется 64х битная математика и размер модуля простых чисел не должен превышать 32х бит.
Правда нет генерации ключей. Эти функции я взял у Z0MBiE.

Т.к. алгоритм генерации простых чисел сожрет очень много процессорного времени, я решил скопипастить таблицу простых чисел во флеш и не парить себе мозг. Далее во время работы случайно дергаю от туда два числа.

1) Как видно из статей для начала нужно перемножить два простых числа. В данном случае результат умножения не должен превышать 32х бит. К выбору случайных чисел подходим ответственно.

Пример:
p=59999;
q=69073;
m = p * q = 4144310927

50% ключа уже готово.

2)Выбираем открытую экспоненту. Которая удовлетворяет условию.

1 < e < (p-1)*(q-1)

При этом e будет нечетной.

При выборе можно:
  • можно использовать алгоритм e+2. А после проверять, чтоб e и (p-1)*(q-1) были взаимно простыми.
  • e можно выбрать из списка простых чисел. Тогда вся проверка на взаимную простоту сведется к
    ((p-1)*(q-1))%e
  • e можно выбрать из списка рекомендуемых. Тогда числа нужно проверять на взаимную простоту но шифрование будет происходить быстрее.
  • любое простое число которое больше половины (p-1)*(q-1)+1. Деление на 2 делаем смещением.


Вот функция нахождение наибольшего общего делителя. С помощью нее делается проверка на взаимную простоту. При правильном e вернет 1.
//GCD(e, (p-1)*(q-1))
huge_t GCD(huge_t x,huge_t y)
{
	 while (1)
	 {
		if (y == 0) return x;
		x = x % y;
		if (x == 0) return y;
		y = y % x;
	 }
}


Эта функция возвращает секретную экспоненту
huge_t modinv(huge_t a,huge_t m)
{
    signed long long b = m;
    signed long long c = a;
    signed long long i = 0;
    signed long long j = 1;

	long long x,y;

	while (c != 0)
	{
		x = b / c;
		y = b % c;
		b = c;
		c = y;
		y = j;
		j = i - j * x;
		i = y;
	}

	if (i < 0) i += m;

	return i;
}


В ней обязательно используются знаковые 64х битные переменные.
a — это открытая экспонента
m — это (p-1)*(q-1)

При моих значениях вышло
publicKey {e=17 n=4144310927 }
privateKey {d=2437754033 n=4144310927 }
Выходит, что размер публичного и приватно ключа 8 байт. Можно схитрить и выбирать открытую экспоненту так, чтоб она была всегда равна 1му байту. Тогда размер публичного ключа будет 5ть байт.

Размер шифруемых данных не должен превышать 2х байт(с округлением до байтов). Т.е. дробим сообщение по два байта и шифруем. Итого размер посылки умножиться на 2.

И все. И главное это работает.

Отлаживать алгоритм лучше на PC а дальше переносить на микроконтроллер.

PS: коменты запрещены. Они меня не интересуют.
PPS: О том насколько это тяжеловесно. Количество итераций на шифрование/дешифрование завист от конкретного ключа. В примере(пример ключей) на шифрование AES128 расходуется 80 итераций и на расшифровку 512. При использовании RSA-64 речь уже будет идти о тысячах итераций.

PPPS: Об оптимизации.

modexp — все входные/выходные параметры являются 32х битными. Но внутри используется возведение в квадрат, поэтому используется 64х битная математика.

GCD — на входе 32х битные параметры. На выходе достаточно и одного байта, но нужно слегка модифицировать код функции.

modinv — на входе/выходе 32х битные параметры. Внутри используется 64х битная математика, также идет работа с отрицательными числами.

В микроконтроллерах лучше вообще отказаться от функций с параметрами. Ясен пень идет речь о фиксированной длине ключа. Все функции должны быть без параметров! Все параметры должны передаваться через глобальные переменные, результат тоже лучше возвращать в глобальную переменную. Также все переменные используемые в функциях должны быть глобальными. Читабельность кода снизится, но производительность возрастет. Т.к. все переменные хранятся в стеке, для работы с ними функция использует косвенную адресацию. Глобальные переменные имеют постоянный адрес, поэтому при использовании их не используется косвенная адресация.
Этот совет имеет смысл, только если используемый микроконтроллер работает быстрее с оперативной памятью чем со стеком. Например в AVR и 8051 используется программный стек, обращение к переменной из виртуального стека занимает намного больше времени чем к глобальной переменной.

И само собой нужно правильно организовать программу. Должен происходить только один вызов функции, внутри которой все функции инлайновые. Так можно сохранить малый размер и высокую производительность.
  • +4
  • 09 января 2013, 01:15
  • a9d

Комментарии (0)

RSS свернуть / развернуть
Автор топика запретил добавлять комментарии