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

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

См. также

Публикаций не найдено

Попробуйте расширить область поиска, проверьте поисковый запрос и повторите попытку.

Или закажите индивидуальную разработку вашего решения.

Создать заказ на разработку