I. Обзор
Поскольку международные алгоритмы, такие как RSA и AES, сталкиваются с риском блокирования алгоритмов высокой интенсивности и развертывания бэкдоров, моя страна разработала набор алгоритмов безопасности для SM2/SM3/SM4/SM9 на основе эллиптических кривых ECC. В соответствии с общей национальной стратегией финансовые и важные области должны постепенно реализовать замену алгоритма национальной тайны.Кроме того, согласно общему плану Народного банка Китая, финансовая индустрия должна полностью применить алгоритм национальной тайны в 2022 году. .
В платформе мобильного финансового развития FireFly предоставляется полный пакет алгоритмов шифрования и дешифрования, который поддерживает алгоритм национальной тайны. Чтобы лучше использовать и продвигать национальный алгоритм шифрования, ниже подробно анализируется принцип шифрования эллиптической кривой ECC.
2. Принцип алгоритма эллиптической кривой
Алгоритм шифрования на основе эллиптической кривой (Elliptic Curve Cryptography) — это метод шифрования с открытым ключом, основанный на теории эллиптических кривых. Эллиптическая кривая над конечным полем Абелевской группы точек неразрешима дискретным логарифмом, шифрованием, дешифрованием и цифровой подписью. Сумматор дискретного логарифма эллиптической кривой соответствующего модульного умножения, который можно соотнести на основе криптосистемы эллиптической кривой.
3. Преимущества алгоритма эллиптических кривых
1. Больше подходит для мобильного интернета
При том же уровне безопасности шифрования длина ключа ECC составляет 163 бита, а длина ключа RSA — 1024 бита. Длина ключа алгоритма шифрования ECC очень мала, что означает меньший объем памяти, меньшую нагрузку на ЦП и меньшую пропускную способность. По мере того, как все больше и больше пользователей используют мобильные устройства для выполнения различных действий в Интернете, алгоритм шифрования ECC обеспечивает лучший клиентский опыт для обеспечения безопасности мобильного Интернета.
2. Лучшая безопасность
Алгоритм шифрования ECC обеспечивает более надежную защиту и может предотвращать атаки лучше, чем другие современные алгоритмы шифрования, делая ваш веб-сайт и инфраструктуру более безопасными, чем традиционные методы шифрования, и обеспечивая лучшую защиту для безопасности мобильного Интернета.
3. Лучшая производительность
Алгоритм шифрования ECC требует более короткой ключевой длины для обеспечения лучшей безопасности.
Четвертое: теоретические основы эллиптической кривой.
Уравнение эллиптической кривой удовлетворено в проективной плоскости
Y2Z + a1XYZ + a3Yz2 = X3+ a2X2Z + a4XZ2 + a5Z3
Множество всех точек, где каждая точка на кривой неособая (или гладкая).
Это уравнение является уравнением Вейерштрасса, которое является однородным уравнением.
Форма эллиптической кривой не является эллипсом. Оно названо потому, что уравнение описания эллиптической кривой аналогично уравнению для вычисления длины окружности эллипса. Вот форма эллиптической кривой:
-
Из определения эллиптической кривой мы можем знать, что эллиптическая кривая гладкая, поэтому обычные точки на эллиптической кривой имеют касательные.
2. Добавление эллиптической кривой на
① Алгоритм
Произвольно возьмем две точки P и Q на эллиптической кривой (если две точки P и Q совпадают, то касательную к точке P) возьмем за прямую, пересекающую другую точку R' эллиптической кривой, а параллельная прямая оси y, проходящая через R', пересекается с R. Условимся, что P+Q=R. (на фото)
② Подробное объяснение алгоритма
-
Здесь + — сложение, абстрагированное от обычного сложения, оно имеет некоторые свойства обычного сложения, но конкретный алгоритм явно отличается от обычного сложения.
К одинаковых точек P складываются вместе, и мы обозначаем это как kP. Как показано на рисунке ниже: P+P+P = 2P+P = 3P, 3P в 3 раза больше точки P.
3. эллиптическая кривая над конечным полем
① Конечное поле
Упомянутая выше эллиптическая кривая определена в поле действительных чисел, а действительные числа непрерывны, что приводит к непрерывности эллиптической кривой, но не подходит для шифрования. Следовательно, эллиптическую кривую нужно превратить в дискретные точки, а эллиптическую кривую нужно определить на конечном поле (как следует из названия, конечное поле — это поле, состоящее только из конечного числа элементов).
Ниже дано конечное поле Fp, имеющее только конечное число элементов.
В Fp 0,1,2...p-2,p-1 всего p (p простое число) элементов;
Правило сложения (a+b) для Fp таково: a+b≡c (mod p), то есть остаток от (a+b)÷p такой же, как остаток от c÷p.
Правило умножения (a×b) для Fp: a×b≡c (mod p);
Правило деления Fp (a ÷ b) равно a / b≡c (mod p), т. е. a × b-1≡c (mod p); целое число между (b-1 равно от 0 до 1 p-, но удовлетворяет b × б-1≡1 (мод р);
Единичный элемент Fp равен 1, а нулевой элемент равен 0.
② Шифруемая эллиптическая кривая
同时，并不是所有的椭圆曲线都适合加密。 у2 = x3 + ax + b — это класс эллиптических кривых, которые можно использовать для шифрования, а также самый простой класс. Поместите у ниже2 = x3
4a3 + 27b2
Тогда все точки (x, y), удовлетворяющие следующему уравнению, плюс бесконечно удаленная точка O∞ образуют эллиптическую кривую.
y2 = x3 + ax + b(mod p)
где x, y принадлежат целым числам от 0 до p-1, и эта эллиптическая кривая обозначается как Ep(a,b).
Пример: смотреть на у2 = x3+ х + 1 (мод 23) изображение
Таким образом, эллиптическая кривая становится дискретной точкой.Эллиптическая кривая будет проявляться по-разному в разных числовых полях, но ее сущность все еще остается эллиптической кривой.
③ Рассчитать координаты точки на эллиптической кривой
Эллиптическая кривая на Fp также имеет сложение.По правилу сложения можно вычислить координаты точки на эллиптической кривой.
Известная точка P (x1, y1), Q(x2,y2), рассчитайте точку R (x3, y3):
X3≡ к2- Икс1- у1 (mod p)
Y3≡ k (x1-маленький3) –у1 (mod p)
Если P≠Q, три точки PQR коллинеарны, и его наклон k=(y2-имеют1) / (x2-маленький1).
Где если P = Q, PR слишком эллиптическая касательная точка P, наклон k = (3x12+ a) / 2y1
Если существует минимальное натуральное число n в точке P на эллиптической кривой, такое что число, умноженное на nP=O∞, то n называется порядком P. Если n не существует, мы говорим, что P бесконечно заказ. На самом деле все точки порядка n на эллиптической кривой, заданной над конечным полем, существуют.
5. Принцип шифрования и дешифрования на эллиптических кривых
1. Основа для шифрования и дешифрования
Общественный ключ алгоритм всегда основан на математической головоломке. RSA основана на примере: Учитывая два числа p, q легко получают путем умножения n, и n относительно сложная факторизация. Так какие проблемы возникают эллиптическая кривая?
Рассмотрим следующее уравнение:
K = кг [где k, g - точка на ep (a, b), k - это целое число меньше, чем n (n - порядка точки g)]]
При заданных k и G легко вычислить K по закону сложения, но при заданных K и G найти k относительно сложно. Это загадка, используемая алгоритмами шифрования на основе эллиптических кривых.
Мы называем точку G базовой точкой, k (k k = 2, K в 2 раза больше точки G; K = 3, K в 3 раза больше точки G; k = 4, K в 4 раза больше точки G; ... Если K кратно G на данной эллиптической кривой, как вычислить, сколько раз K кратно G? Интуитивно легко вычислить кратную точку в прямом направлении, но гораздо сложнее вычислить точку K, кратную G в обратном направлении. Поэтому в алгоритме эллиптической кривой в качестве закрытого ключа используется кратное k, а в качестве открытого ключа — K.
Теперь мы опишем процесс зашифрованной связи с использованием эллиптических кривых: Пользователь выбрал эллиптическую кривую Ep (a, b) и взял точку на эллиптической кривой за точку G. Пользователь A выбирает закрытый ключ K и генерирует открытый ключ K = kg. 1=М+рК;С2=rG. Пользователь B будет C1, C.2пользователю А. После того, как пользователь A получит информацию, вычислите C1-kC2, результатом является точка М. потому что C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M Затем декодируйте точку M, чтобы получить открытый текст. В этом зашифрованном сообщении, если есть вуайерист H, он может видеть только Ep(a,b), K, G, C1, С2Через K, G k требуется или C2, G и r относительно сложны. Следовательно, H не может получить информацию открытого текста, передаваемую между A и B.
В криптографии для описания эллиптической кривой на Fp обычно используются шесть параметров: T=(p,a,b,G,n,h). p , a , b используются для определения эллиптической кривой, G – базовая точка, n – порядок точки G, h — целая часть числа m, деленная на n всех точек эллиптической кривой. Значение этих параметров для выбора прямого воздействия на безопасность шифрования. Значения обычно требуются для удовлетворения следующих условий: п конечно, тем выше безопасность, но больше скорость расчета будет замедляться, около 200 для удовлетворения общих требований безопасности; р≠n×ч; pt≠1 (mod n), 1≤t 4a3 + 27b2≠ 0 (мод р); n — простое число; ч≤4.
Алгоритм цифровой подписи на эллиптических кривых (ECDSA) является аналогом алгоритма цифровой подписи (DSA) с использованием пароля на эллиптических кривых (ECC). ECDSA представляет собой комбинацию ECC и DSA, весь процесс подписи аналогичен DSA, разница в том, что в подписи используется алгоритм ECC, а конечное подписанное значение также делится на r и s.
Выберите эллиптическую кривую Ep(a,b) и базовую точку G; Выберите закрытый ключ k (k Сгенерировать случайное целое число r (r В качестве параметров взять исходные данные и значения координат x, y точки R, и вычислить SHA1 как хеш, то есть Hash=SHA1(исходные данные, x, y); Вычислить s≡r - Hash * k (mod n); В качестве значений подписи используются r и s. Если одно из r и s равно 0, выполнение снова начинается с шага 3.
Получив сообщение (m) и значение подписи (r, s), получатель выполняет следующие операции: Если уравнение выполняется, подпись принимается, в противном случае подпись недействительна. Алгоритмы эллиптического шифрования имеют широкий спектр приложений, таких как TLS, openPGP и SSH, а также широко используются в биткойнах и других зашифрованных цифровых валютах. Кроме того, национальный секретный алгоритм SM2, который в основном продвигается в моей стране, также основан на алгоритме эллиптической кривой. Ниже в качестве примеров используются SM2 и TLS:
① Обзор И алгоритм SM2, и алгоритм RSA являются криптографическими алгоритмами с открытым ключом. С развитием криптографии и вычислительных технологий обычно используемый 1024-битный алгоритм RSA сталкивается с серьезными угрозами безопасности. После исследования наш национальный отдел управления криптографией решил использовать эллиптический SM2. алгоритм кривой, чтобы заменить его Алгоритм RSA. Алгоритм SM2 имеет преимущества в безопасности и производительности.См. Таблицу 1 для времени прорыва алгоритма и Таблицу 2 для производительности алгоритма. Надежность ключа RSA Сила ключа эллиптической кривой сломать ли 512 106 Он был скомпрометирован 768 132 был взломан 1024 160 2048 210 Таблица 1 Время атаки алгоритма алгоритм Скорость подписи (раз/сек) Скорость проверки подписи (раз/сек) 1024-битный RSA 2792 51224 2048 ЮАР 455 15122 256-битный СМ2 4095 871 Таблица 2. Производительность алгоритма ② Связь между SM2 и алгоритмом эллиптической кривой Уравнение эллиптической кривой, используемое алгоритмом SM2, имеет вид: y2= x3+ ax + b, в стандарте алгоритма SM2 путем указания коэффициентов a и b определяется уникальная стандартная кривая. В то же время, чтобы сопоставить кривую с алгоритмом шифрования, в стандарте SM2 также определяются другие параметры для использования программой алгоритма. ③ Процесс шифрования и дешифрования SM2 Ниже приведены сокращения символов, используемые в процессе шифрования и дешифрования SM2: A, B Два пользователя, использующие криптосистему с открытым ключом. Закрытый ключ пользователя БД B. E(Fq) Множество всех рациональных точек (включая бесконечно удаленную точку O) эллиптической кривой E на Fq. Состоит из конечного поля Fq q элементов. G Базовая точка эллиптической кривой, порядок которого представляет собой простое число. Хэш () криптографический хеш алгоритм. HV() дайджест сообщения длиной v бит криптографический хеш-алгоритм. O Особая точка на эллиптической кривой, называемая точкой бесконечности или нулем, является единичным элементом аддитивной группы эллиптических кривых. PB Открытый ключ пользователя B. q Количество элементов в конечном поле Fq. Элементы в A, B FQ определяют эллиптическую кривую E на FQ. x||y Конкатенация x и y, где x и y — строки битов или строк байтов. [k]P точка k умножается на точку P на эллиптической кривой. E(Fq) Число точек на E(Fq) называется порядком эллиптической кривой E(Fq). M⊕t XOR Операция а. Алгоритм шифрования процесса A2: Рассчитайте точку эллиптической кривой C1 = [k]G=(x1, y1) в соответствии с Алгоритмом шифрования с открытым ключом на эллиптической кривой SM2, часть 1, 3.2.9 и 3.2.5. метод, преобразуйте тип данных C1 в битовую строку; A3: Рассчитать точку эллиптической кривой S= [h]PB, если S является бесконечной точкой, сообщить об ошибке и выйти; A4: Рассчитайте точку эллиптической кривой [k]PB=(x2, y2), как указано в 3.2.6 и 3.2.5 части 1 Алгоритма шифрования с открытым ключом на эллиптической кривой SM2. метод преобразования типов данных координат x2 и y2 в битовые строки; A5: Вычислить t = KDF(x2||y2, klen), если t является строкой, состоящей только из нулей, вернуть A1; A6: вычислить C2=M⊕t; A7: Рассчитать C3= Хэш (x2||M|| y2); A8: выводит зашифрованный текст C = C1 || C3 || C2. Рекомендуемая главная SM2 эллиптическая кривая криптографии криптографического ключа SM2, сначала генерирует случайное число, рассчитанное кривой BigInteger Cruve C1,2 большое количество 32бай, т.е. 1 часть результата шифрования SM2. Часть 2 - настоящий зашифрованный текст, результат является зашифрованным открытым текстом, открытым текстом и одинаковой длины. Часть 3 - это хеш-значение для данных эффективности. Рекомендуемые по стране Закрыть эллиптическую кривую 256, результат шифрования открытого текста будет больше, чем первоначальная длина 96BYTE. Чтобы расшифровать зашифрованный текст C=C1||C3||C2, пользователь B как дешифратор должен выполнить следующие шаги операции: B1: Возьмите битовую строку C1 из C в соответствии с методом, описанным в 3.2.4 и 3.2.10 Алгоритма шифрования с открытым ключом на основе эллиптических кривых SM2, часть 1, Преобразуйте тип данных C1 в точку на эллиптической кривой, проверьте, удовлетворяет ли C1 уравнению эллиптической кривой, и сообщите об ошибке, если нет и выйти; B2: Рассчитать эллиптическую точку кривой S = [H] C1, если S - бесконечная точка, сообщите об ошибке и выходе; B3: Рассчитайте [дБ]C1= (x2, y2) в соответствии с методом, приведенным в 3.2.6 и 3.2.5 Части 1 Алгоритма шифрования с открытым ключом на основе эллиптических кривых SM2, Типы данных координат x2, y2 преобразуются в битовые строки; B4: Вычислить t = KDF(x2||y2, klen), если t является строкой, состоящей только из 0 бит, сообщить об ошибке и выйти; B5: взять битовую строку C2 из C и вычислить M’=C2⊕t; B6: вычислить u = Hash (x2||M’|| y2), вынуть битовую строку C3 из C, если u≠C3, сообщить об ошибке и выйти; B7: вывод открытого текста M'. Расшифровка SM2 также может быть реализована с использованием мягких алгоритмов. Однако, поскольку он включает в себя работу с закрытым ключом, для защиты безопасности закрытого ключа рекомендуется запускать его на аппаратном устройстве, таком как UKey и других носителях, которые могут лучше защитить безопасность ключа. Возьмем, к примеру, шифрование файлов. Сначала зашифруйте с помощью сертификата шифрования в UKey, эту часть можно выполнить в прикладной системе. Для расшифровки сертификат шифрования, соответствующий UKey, может быть расшифрован.Прикладная система вызывает интерфейс расшифровки UKey для завершения расшифровки данных на физическом оборудовании и может быть защищена PIN-кодом устройства. ④ Скорость и длина результата алгоритма SM2 Проще говоря, скорость подписи SM2 высокая, а скорость проверки подписи низкая, что прямо противоположно характеристикам алгоритма RSA. См. Таблицу 2 выше. Кроме того, скорость шифрования и дешифрования сравнима со скоростью проверки подписи. SM2 поддерживает длину данных почти 128 ГБ, а зашифрованный результат увеличивается на 96 байт. Алгоритм подписи SM2 не имеет ограничений на длину исходных данных, а результат подписи составляет 64 байта.
① Обзор HTTPS обеспечивает три функции: шифрование контента, аутентификацию личности и целостность данных через уровень TLS и механизм сертификатов, которые могут эффективно предотвращать мониторинг или подделку данных, а также могут противостоять атакам MITM (человек посередине). При реализации шифрования TLS требуются два алгоритма: асимметричный обмен ключами и симметричное шифрование содержимого. Сила шифрования симметричного контента очень высока, скорость шифрования и дешифрования также высока, но невозможно безопасно генерировать и хранить ключи. В протоколе TLS данные приложения передаются после симметричного шифрования, а симметричный ключ, используемый при передаче, получается путем обмена асимметричным ключом на этапе установления связи. ② алгоритм обмена ключа TLS Наиболее часто используемым алгоритмом обмена ключа RSA и ECDHE: RSA имеет долгую историю, хорошую поддержку, но не поддерживает PFS (идеальная прямая секретария); и ECDHE - это использование ECC (эллиптическая кривая) DH (диффуз Алгоритм, вычислительная скорость, поддержка PFS. ③ алгоритм ключа на основе ECC Ниже приведены пять общих алгоритмов обмена ключами TLS на основе ECC, которые Mimic DH_DSS, DHE_DSS, DH_RSA, DHE_RSA и DH_ANON. Примером ECDHE_ECDSA: Сертификат содержит открытый ключ с поддержкой ECDSA, который использует алгоритм ECDHE для согласования подготовленного главного ключа; сертификат должен разрешать использование ключа для подписи с использованием алгоритма хеширования, который будет использоваться в сообщении обмена ключами сервера; открытый ключ должен использовать ключ, который может поддерживаться клиентом. Для форматов кривых и точек клиент указывает поддерживаемые именованные кривые с помощью расширения ec_point_formats в приветственном сообщении клиента, как описано в [TLSECC]. Это самый безопасный и высокопроизводительный набор шифров в TLS 1.2. ④ Полный процесс обмена ключами ECDHE A: Клиент отправляет клиента Hello на сервер для информирования сервера версии протокола, шифрной набор и другой информации, поддерживаемой клиентом. B: а) сервер получает ответ, выбирает протокол и набор, поддерживаемые обеими сторонами, отправляет клиенту приветствие сервера, а также сервер отправляет клиенту свой собственный сертификат (Certificate). Б. Сервер использует закрытый ключ для подписи случайного числа клиента, случайного числа сервера и параметров DH сервера для создания подписи сервера. C: Сервер отправляет параметры DH сервера и подпись сервера (обмен ключами сервера) клиенту. D: клиент отправляет параметр DH клиента (обмен ключами клиента) на сервер. После этого клиент использует открытый ключ для проверки подписи сервера.Клиент и сервер используют параметры DH сервера и параметры DH клиента для генерации предварительного мастер-ключа, а затем используют предварительный мастер-ключ, клиент случайный число и случайное число сервера для генерации главного ключа (сеансового ключа). Наконец, рукопожатие завершено, и все сообщения шифруются мастер-ключом. Как показано на рисунке: Алгоритм эллиптической кривой ECC, основанный на теории эллиптических кривых, может обеспечить более высокий уровень безопасности при меньшей вычислительной мощности для эффективного решения «надежности, необходимой для увеличения длины ключа безопасности» проблем реализации проекта, и получил широкую поддержку и использование читателей, когда выбирая алгоритм шифрования, алгоритм ECC был бы хорошим выбором. Введение в алгоритм шифрования ECC https://www.pediy.com/kssd/pediy06/pediy6014.htm Elliptic Curve Cryptography: a gentle introduction https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ Государственное управление криптографии http://www.oscca.gov.cn/ Национальная коммерческая криптография (1) SM2 Алгоритм шифрования с открытым ключом на основе эллиптических кривых http://www.firstsolver.com/wordpress/?p=1938 TLS_ECC https://tools.ietf.org/html/rfc4492 2. Процесс шифрования и дешифрования
3. Параметры шифрования и дешифрования
VI. Эллиптическая кривая цифровой подписи принцип (ECDSA)
1 Обзор
2. Процесс подписания
3. Процесс проверки визы
VII. Эллиптическая кривая алгоритм
1. SM2
2. TLS
8. Заключение
9. Ссылки
об авторе