Криптография (шифрование) на эллиптических кривых

Публикация № 1357015

Разработка - Защита и шифрование

Криптография ЭллиптическаяКриптография Шифрование

Тема шифрования сейчас очень популярна, а шифрование на эллиптических кривых является топом, поскольку считается одним из самых надежных криптографических алгоритмов (и поэтому используется в Bitcoin и других криптовалютах, SSL протоколе и т.д.). У меня же возник интерес - а возможно ли реализовать шифрование на эллиптических кривых средствами 1С... и теперь мне известен ответ.

Спросите программиста 1С - а можно ли сделать шифрование, как в Bitcoin, на 1С?... и думаю, что услышите про большие числа, сложности вычисления, неориентированность платформы 1С на решение таких задач. По крайней мере, такие ответы слышал я, поэтому решил проверить все самостоятельно. 

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

Теория эллиптического шифрования

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

Проблема проста - двое пользователей хотят безопасно обменяться информацией. Обычно в литературе этих пользователей называют Боб и Алиса, хотя реально это может быть: бухгалтер, сдающий электронную отчетность и налоговая служба; клиент банка, оплачивающий покупки электронной картой и банковская система, фиксирующая и обрабатывающая транзакции; трейдер, покупающий bitcoin и ферма, получающая его запрос и т.д.

Суть криптографической защиты заключается в том, что если злоумышленник перехватит отсылаемое сообщение (например, через сомнительный Wi-Fi в случае оплаты через телефон или с помощью вирусной программы, перехватывающей отсылаемые сообщения с компьютера), то он не сможет её расшифровать и изменить. А то представьте, что было бы без защиты – клиент отсылает информацию банку о переводе 100 рублей другому клиенту, злоумышленник перехватывает данное сообщение и меняет в нем сумму с 100 рублей на 100 тыс. рублей, так же меняет счет получателя на свой и отсылает это сообщение дальше в Банк, Банк без проверки проводит транзакцию… От подобных действий злоумышленников спасает криптографическая защита.

Работает криптография очень интересно – у каждой стороны обмена сообщения существует открытый (H) и закрытый ключ (d). Причем, открытый ключ видят все участники (он как номер банковской карты или номер телефона), закрытый ключ – это как бы секретный пароль, который знает только пользователь.

Есть два основных алгоритма использования криптографических ключей:

1) формируется общий секретный ключ по данным открытых ключей отправителя и получателя и закрытого ключей отправителя. В этом случае происходит шифрование сообщения с помощью общего секретного ключа с преобразованием сообщения в нечитаемую последовательность символов. Злоумышленник, перехвативший сообщение, зная только открытые ключи отправителя и получателя и не зная закрытого ключа, не сможет его расшифровать. Получатель же сможет вычислить общий секретный ключ и расшифрует сообщение.

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

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

 

Краткое описание эллиптического шифрования

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

Кривые шифрования чуть сложнее изучаемых в школе и называются эллиптическими кривыми. Они имеют вид:

y2 = x3 + ax + b

Поскольку для криптографических целей достаточно коллекции нужных точек (а не все точки кривой), то кривую ограничивают, добавляя модуль:

y2 = x3 + ax + b (mod p)

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

Первое - это то, что для эллиптических кривых существует правило: если провести прямую, пересекающую 3 точки кривой, то сумма точек пересечения будет равна 0.

P + Q + R = 0.

Это же уравнение можно представить как:

P + Q = -R

и переформулировав правило: результатом сложения двух точек графика, будет обратная величина третьей точки. Это уравнение работает, даже если одна из точек станет касательной (как это выглядит графически, смотрите на логотипе публикации ;-) ).

Второе – это то, что эллиптические кривые имеют одну интересную особенность, называемую цикличность. Заключается оно в том, что производя поочередные умножения точки на переменную, значения координат точек через ряд умножений начнет повторяться. И тут мы получаем важные параметры:

- Базовая точка эллиптической кривой (G), т.е. это первая точка, вычисленная после точки с координатой (0, 0). 

- Порядок кривой (n), т.е. значение переменной, начиная с которой начинаются повторения координат точек.

Так вот, открытые и закрытые ключи формируются на одинаковой эллиптической кривой, для которой известна Базовая точка (G), Порядок кривой (n) и другие параметры (которые опускаю, что бы не усложнять описание). Эти параметры постоянны для каждой отдельной эллиптической кривой и известны всем участникам обмена.

Закрытый криптографический ключ (d) – это случайное число в диапазоне от 1 до порядка кривой (n), т.е. до количества сложений базовой точки (G), после которых точки начинают повторяться.

Открытый криптографический ключ (H) – это точка эллиптической кривой, которая получается после умножения Базовой точки (G) на d (значение закрытого криптографического ключа).

Более подробное описание вы сможете найти в специализированной литературе и в интернете.

 

Пример эллиптического шифрования

 

Например, для эллиптической кривой

y2 = x3 + 2x + 3 (mod 97)

базовая точка P = (3, 6), порядок кривой n = 5, поскольку

1 2 3 4 5
0*P = (0, 0);

1*P = (3, 6);

2*P = (80, 10);

3*P = (80, 87);

4*P = (3, 91);

5*P = (0, 0);

6*P = (3, 6);

7*P = (80, 10);

8*P = (80, 87);

9*P = (3, 91);

(формулы не привожу для упрощения изложения, найти их сложности не предоставит)

Видно, что для такой кривой можно задать Закрытый ключ (d) в диапазоне от 0 до 4, например 3. Тогда Открытый ключ (H), исходя из таблицы, будет (80, 87).

Предвижу вопрос - ну что это за пароль в диапазоне от 0 до 4-х? Это не серьезно – сложив базовую точку с самой собой максимум 4 раза мы взломаем систему!

Абсолютно согласен, это очень простая криптографическая кривая, на которой можно понять основы криптографии (кстати, в обработке вы можете протестировать работу криптографии на эллиптических кривых и на приведенном тут примере, для этого необходимо в модуле "ПриСозданииНаСервере" раскомментировать параметры рассматриваемой кривой).

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

y2 = x3 + 7 (mod 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f)

(не пугайтесь, 0xfff.. – это цифры в 16-иричном представлении)

имеющая порядок:

n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141

и базовую точку (G):

Gx = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798

Gy = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8

Страшно? Не пугайтесь, 0xfffff… - это цифры в 16-ричном представлении.

Вот на этой кривой и будут формироваться ключи в приложенной обработке.

Задача получения и проверки открытого ключа H(x, y), путем умножения базовой точки G(x, y) на закрытый ключ (d) легко решается современными компьютерами за доли секунд, поскольку носит вычислительный характер.

Как вы считаете, а насколько быстро можно подобрать такой закрытый ключ (d), что бы умножив базовую точку кривой G (x, y) на закрытый ключ (d), получить открытый ключ пользователя H(x, y)?

Давайте скажу ответ… На текущий момент, задача подбора закрытого ключа (d), зная значение базовой точки G(x, y) и открытого ключа H(x, y) является сложной, с которой современные компьютеры не справляются (перебор всех возможных значений приведенной кривой на всех компьютерах и гаджетах, существующих на нашей планете, занял бы время в несколько миллиардов лет), поэтому приведенный криптографический алгоритм считается надежным. Хотя, есть мнение, что квантовые компьютеры эту задачу будут решать за более короткое время... посмотрим.

 

Практика эллиптического ши фрования

Ну и наконец, давайте рассмотрим, как работает обработка.

Формирование ключей производится на эллиптической кривой, параметры которой указаны в поле "Параметры кривой" (внизу обработки). Следует обратить внимание, что формула кривой приводится в 16-ричном представлении, а все параметры пересчитаны в 10-ричное представление.

Поскольку сообщения будут пересылаться между двумя пользователями одной системы, то необходимо сформировать закрытые (секретные) и открытые ключи для каждого из них. Для этого необходимо кликнуть на "Сформировать ключ мой" (и сформировать ключи первого участника обмена) и "Сформировать ключ твой" (и сформировать ключи второго участника обмена).

Будет выполнена следующая процедура:

&НаКлиенте
Процедура СформироватьКлючМой(Команда)
	
	ТочкаГрафика = Новый Структура("X,Y", Объект.gx, Объект.gy);
	
	КлючиСформированы = 3; //Количество попыток формирования ключей
	
	Пока КлючиСформированы > 0 Цикл
		
		ЗакрытыйКлюч10 = СформироватьЗакрытыйКлюч();
		Объект.ЗакрытыйКлючМой = Строка(Формат(ЗакрытыйКлюч10, "ЧГ=0"));			
		
		ОткрытыйКлюч10 = УмножитьКлючНаТочку(ЗакрытыйКлюч10, ТочкаГрафика);
		
		Если Не ЗначениеЗаполнено(ОткрытыйКлюч10) Тогда
	    	КлючиСформированы = КлючиСформированы - 1;
			Сообщение = Новый СообщениеПользователю;
			Сообщение.Текст = "Для закрытого ключа """ + ЗакрытыйКлюч10 + """ открытый ключ не сформирован! Попробую переформировать ключи...";
			Сообщение.Сообщить();
		Иначе	
			Прервать;
		КонецЕсли;
		
	КонецЦикла;
	
	Если ЗначениеЗаполнено(ОткрытыйКлюч10) Тогда
		Объект.ОткрытыйКлючМой_X = СтрЗаменить(ОткрытыйКлюч10.X, Символ(160), "");
		Объект.ОткрытыйКлючМой_Y = СтрЗаменить(ОткрытыйКлюч10.Y, Символ(160), "");
	Иначе
		Сообщение = Новый СообщениеПользователю;
		Сообщение.Текст = "Ключи не сформированы. Попробуйте ещё раз!";
		Сообщение.Сообщить();
	КонецЕсли; 
		
КонецПроцедуры

То есть, формируется закрытый ключ (d) через генератор случайных чисел в 10-ричном представлении (ЗакрытыйКлюч10), размером от 40 до 75 цифр. Далее, базовая точка кривой (G) (значения "x", "y" в параметрах кривой) умножается на значение закрытого ключа (d(по другому говоря, складывается сама с собой ЗакрытыйКлюч10 раз) и вычисленная таким образом координата будет являться открытым ключом (H). Теория алгоритма умножения базовой точки эллиптической кривой на параметр, достаточно обширна и выходит за рамки текущей публикации (обратитесь к специализированной литературе).

1. Что бы проверить правильность формирования криптографических ключей, сформируем и посмотрим общие секретные ключи пользователей. Секретный ключ пользователя формируется по данным его закрытого ключа и открытого ключа получателя, с которым производится обмен сообщением. 

Сформируем общие секретные ключи пользователей, нажимая "Показать секретный ключ (мой)" и "Показать секретный ключ (твой)". Показанные в сообщении секретные ключи должны совпасть:

Что бы показать как можно воспользоваться общими секретными ключами для шифрования сообщений, в обработке предложен простой алгоритм:

...	
    // Формируем исходную строку шифрации
	ИсходнаяСтрокаШифрации = ОбщийСекретныйКлюч.X + ОбщийСекретныйКлюч.Y;
	ДлинаСтрокиШифрации = СтрДлина(ИсходнаяСтрокаШифрации);
	
	//Шифруем текст
	ОчереднаяСтрокаШифрации = "";
	СтрокаЗашифрованная = "";
	Для СимволТекста = 1 По СтрДлина(ТекстДляШифрации) Цикл
		
		ОчереднойСимвол = КодСимвола(ТекстДляШифрации, СимволТекста);
		
		Для СмещениеШифра = 0 По 3 Цикл 
			НомерСимволаШифра = (СимволТекста * 4 - 3 + СмещениеШифра) % ДлинаСтрокиШифрации; 
		    ОчереднаяСтрокаШифрации = ОчереднаяСтрокаШифрации + Сред(ИсходнаяСтрокаШифрации, НомерСимволаШифра, 1);
		КонецЦикла;
		
		СтрокаИсходная = Строка(Формат(ПобитовоеИсключительноеИли(Число(ОчереднойСимвол), Число(ОчереднаяСтрокаШифрации)),"ЧЦ=5; ЧВН=; ЧГ=0"));
		СтрокаЗашифрованная = СтрокаЗашифрованная + СтрокаИсходная;
		
		ОчереднаяСтрокаШифрации = ""; 
		
	КонецЦикла;
		
	//Преобразуем зашифрованную строку в разрядность 36
	СтрокаЗашифрованнаяВСимволах = DecToAny(Число(СтрокаЗашифрованная), 36);
...

т.е., код Unicode каждого символа передаваемого сообщения соединяем через ПобитовоеИсключительноеИли (XOR) с 4-мя очередными символами из строки шифрации, состоящей из соединения двух координат секретного ключа. Т.е. для секретных ключей, приведенных в примере на картинке выше, будет формироваться следующая строка шифрования:

СтрокаЗашифрованная = Строка(ПобитовоеИсключительноеИли(Unicode1Символа, 7191)) + Строка(ПобитовоеИсключительноеИли(Unicode2Символа, 0953)) + Строка(ПобитовоеИсключительноеИли(Unicode2Символа, 2097)) + ...

Стоит отметить, что в результате выполнения ПобитовоеИсключительноеИли() с двумя 4-хзначными цифрами возвращается 5-значное число.

Для выполнения шифрования необходимо написать текст в поле "Передаваемый текст" и нажать "Зашифровать".

 

В результате будет получена зашифрованная строка цифр (2 строка в поле "Текст зашифрованный") в 10-ричном представлении, которая преобразуется в 36-иричную систему исчисления (1 строка в поле "Текст зашифрованный"). Соответственно, первая строка и будет передаваться получателю для дешифрации.

Для расшифровки строки необходимо нажать кнопку "Расшифровать". Дешифрация выполняется в обратном порядке: выполняется преобразование строки из 36-ричной в 10-ичную систему исчисления с последующей дешифрацией через XOR очередных 5 символов сообщения с очередными 4-мя символами общего секретного ключа.

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

Первые две строчки в поле "Текст зашифрованный" будут координатами цифровой подписи, полученными по значению хеша передаваемого сообщения и закрытого ключа отправителя. Алгоритм формирования цифровой подписи можно посмотреть в обработке. Функции проверки цифровой подписи исключены из обработки по ряду причин (да, текста расшифровки, указанной на картинке, не будет!), если данный функционал интересен, пишите... )))

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

Храните свои секреты под надежной защитой!!!

 

P.S. Прошу учесть, что я разработчик и совсем не специалист по шифрованию, поэтому прошу сильно не "забрасывать помидорами" за какие-либо мелкие неточности.

 

Тестирование проводил на платформе 8.3.14.1993.

Скачать файлы

Наименование Файл Версия Размер
Шифровальщик на эллиптических кривых

.epf 13,71Kb
2
.epf 1.1.1 13,71Kb 2 Скачать

Специальные предложения

Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Поручик 4460 12.01.21 14:48 Сейчас в теме
В школе любимым занятием было вычислять координаты, то есть решать уравнения, и рисовать на миллиметровке гиперболы и параболы. Миллиметровка тогда была некоторым дефицитом. В основном доставали через знакомых в проектных или строительных конторах.
2. saa@kuzov.org 13.01.21 12:09 Сейчас в теме
Ваша статья подарила надежду, что получится организовать bcrypt средствами свежих версий 1с 8. Скажите, пожалуйста, у Вас есть уже такой опыт?
3. ikar-nikolay 94 13.01.21 13:26 Сейчас в теме
bcrypt - это алгоритм более продвинутого хеширования. К эллиптическому шифрованию имеет косвенное отношение - как переводчик из символов сообщения в число... )))
А вообще, согласен, что нужно идти в ногу со временем и все лучшие практики делать типовым функционалом 1С, тем более уже есть аналоги данного алгоритма в других языках программирования.
4. Eremkin 14.01.21 20:48 Сейчас в теме
Ну все, сейчас скачают обработку и развернут майниг-фермы на своих серверах 1С )))
5. ikar-nikolay 94 15.01.21 00:57 Сейчас в теме
(4) Ну, если честно, то задумка была разработать свою криптовалюту на 1С, даже название придумал "1С-coin" )))).
Мобильный клиент 1С своими последними обновлениями способствует реализации задуманного, алгоритм майнинга и хранения цепочек блокчейна в объектах 1С уже продуман, осталось только реализовать... может в свой следующий отпуск (в апреле) займусь этим творчеством.
Потому, вполне возможно, что будет именно так, как вы и написали. Причем будет майниться валюта 1С, которая будет обмениваться по определенному курсу со старт-мани. )))
6. SerVer1C 357 18.01.21 10:54 Сейчас в теме
(5) М-да... Вашу крипту похачат с помощью одной видеокарты...
7. ikar-nikolay 94 18.01.21 12:58 Сейчас в теме
(6) естественно, такая крипта не для реала (наше законодательство не дружелюбно к таким активностям), а в целях самообразования. Поэтому, похачат, так похачат... хотя не уверен, что так просто, как вами описано. )))
Оставьте свое сообщение