Криптографические протоколы на эллиптических кривых
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
зводительности, так как она определяет необходимый размер параметров шифрования и ключа, что в свою очередь сказывается на производительности всего алгоритма в целом.
Алгоритмы решения задачи факторизации целых чисел. Частным случаем проблемы факторизации целых чисел является задача разложения целого числа n на два простых числа размера l/2 бит. Размер входных данных - O(l) бит. Быстрейший известный алгоритм факторизации n - Number Field Sieve (NFS) имеет субэкспотенциальное ожидаемое время работы.
Ln [1/3, 1.923], где Ln[a ,c] = O()
Алгоритмы решения задачи дискретного логарифмирования. В задаче дискретного логарифмирования параметрами являются числа p и q, где p - простое число размером l бит и q - простой делитель числа p-1 размера t. Размер входных данных равен O(l) бит. Быстрейшими алгоритмами решения такой задачи являются Number Field Sieve (NFS) с ожидаемым временем работы Ln [1/3, 1.923] и Pollards rho algorithm с ожидаемым временем работы
Выбор наиболее эффективного алгоритма зависит от размера входных данных.
Алгоритмы для решения задачи дискретного логарифмирования эллиптических кривых. Целью задачи является целое число d ? [1,n?1], такое, что Q = dP, где n - простое число размером t бит, P - точка порядка n эллиптической кривой над полем GF(p), и Q принадлежит циклической подгруппе, порожденной точкой P. Если положить n ? p, как обычно и бывает на практике, то размер входных данных составляет O(t) бит. Быстрейший алгоритм решения данной проблемы - Pollards rho algorithm, который имеет ожидаемое время работы
Как видно, сложность математической проблемы для всех трех алгоритмов сравнима. Самым важным преимуществом ECDSA является возможность его работы на значительно меньших полях GF(p). Предполагается, что битовый размер открытого ключа, который будет необходим для ECDSA, равен двойному размеру секретного ключа в битах. Ниже приведена таблица сравнения размера параметров ECDSA, RSA и DL для стандартных ключей длины 80 (SKPJACK), 112 (Triple-DES), 128 (AES-small), 192 (AES-medium), 256 (AES-large).
Параметры80 (SKPJACK)112 (Triple-DES)128 (AES-small)192 (AES-medium)256 (AES-large)q (DL)160224256384512n (EC)160224256384512n (RSA)102420483072819215360p (DL)102420483072819215360
Таблица демонстрирует что в алгоритмах ECC могут быть использованы параметры намного меньше размера, чем в RSA и DL при достижении того же уровня безопасности. При этом разница в размере параметров растет с увеличением уровня безопасности. Соответственно, операции в алгоритмах ECC протекают намного быстрее, чем в RSA и DL.
Заключение
В данной работе изложены базовые понятия теории эллиптических кривых, необходимые для реализации криптографических протоколов. Рассмотрены основные алгоритмы арифметики точек эллиптической кривой, а также способы генерации кривых, пригодных для использования в криптографических алгоритмах. Даны алгоритмы шифрования Эль-Гамаля и ЭЦП с использование эллиптических кривых, а в приложение вынесен пример реализации схемы цифровой подписи ECDSA на языке Java с подробными комментариями.
Как следует из последнего раздела данной работы, основным преимуществом эллиптической криптографии является малый размер ключа относительно других схем асимметричного шифрования. Это свойство особенно важно при реализации криптографических протоколов в условиях ограниченности ресурсов памяти и производительности, например при программировании смарт-карт. Также ясно, что с улучшением производительности компьютеров шифры постепенно будут становиться все более уязвимыми при малых длинах ключа. А с увеличение длины ключа преимущества схем на эллиптических кривых над другими схемами шифрования возрастает многократно. За счет меньшей длины ключа возрастает и эффективность вычислительных процессов. Также следует отметить, что помимо общих алгоритмов арифметики эллиптических кривых, существует много специфических алгоритмов, разработанных для кривых специального вида (например, кривых Коблица), которые позволяют добиться еще большего преимущества в эффективности.
Список использованных источников
1. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы. А. А. Болотов [и др.]. - М.: КомКнига, 2006. - 328 с.
. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. А. А. Болотов [и др.]. - М.: КомКнига, 2006. - 280 с.
. Hankerson D. Guide to Elliptic Curve Cryptography. Darrel Hankerson, Alfred J. Menezes, Scott Vanstone. - New York:Springer, 2004. - 332 с.
. Anoop Deoras K. Implementation of elliptic curve cryptography. Anoop K. Deoras. - Pune: Electronics and Telecommunication, Government College of Engineering, 2008 - 77 с.
. Peters С. Counting points on elliptic curves over Fq / Christiane Peters. - New York:DIAMANT, 2008 - 30 с.
. Turki F. Al-Somani. Performance Evaluation of Elliptic Curve Projective Coordinates with Parallel GF(p) Field Operations and Side-Channel Atomicity / Turki F. Al-Somani // JOURNAL OF COMPUTERS, VOL. 5 - Saudi Arabia., 2010 - 99-109 c.
. Amoop M.S. Elliptic Curve Crypthography - An Implementation Tutorial. Anoop M.S. - Thiruvananthapuram.: Tata Elxsi Ltd, 2011. - 11 c.
. Washington, Lawrence C. Elliptic Curves: Number Theory and Cryptography / Lawrence C. Washington. - 2-е изд. - Maryland: University of Maryland, 2008. - 524 c.