Сайт о программировании, математике и моделировании
Записи с метками криптография
Простые числа в криптографии
29 Январь
Все используемые сегодня криптосистемы с открытым ключом опираются на один из следующих типов необратимых преобразований:
Разложение больших чисел на простые множители и работа с простыми числами
Вычисление логарифма в конечном поле.
Вычисление корней алгебраических уравнений.
Таким образом, простые числа являются одной из неотъемлемых частей современных асимметричных криптосистем, то есть систем, использующих два ключа: открытый и секретный. Для того, чтобы криптосистема была стойкой к вскрытию, в ней необходимо использовать простые числа большой длины ( и выше).
Для того, чтобы использовать большие простые числа, их необходимо сначала построить. Читать дальше >
Длинная арифметика
3 Декабрь
Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать, так как для представления чисел в компьютере используются стандартные типы данных. Поэтому в некоторых случаях мы сами должны позаботиться о представлении чисел в машине и о точном выполнении арифметических операций над ними.
Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются «длинными». Реализация арифметических операций над такими «длинными» числами получила название «длинной арифметики». Читать дальше >
Литература по программированию и криптографии
1 Декабрь
- Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черёмушкин А.В. Основы криптографии. М.: Гелиос АРВ, 2002. 2-е изд.
- Бондарев, Рублицкий, Качко. Основы программирования.
- Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.:МЦНМО, 2003.—328 с.
- Василенко О.Н. Применение круговых полей в криптосистемах RSA // IV Международная конференция «Современные проблемы теории чисел и ее приложения». Тула ,10-15 сентября, 2001 /Тезисы докладов. С 36—37. Читать дальше >
РО-алгоритм Полларда — алгоритм для факторизации чисел
1 Декабрь
В криптографии факторизацией называют разложение числа на простые множители. На предположении о вычисления сложности данного процесса основывается криптостойкость некоторых алгоритмов шифрования с открытым ключом, таких, как RSA, алгоритм на эллиптических кривых. Существует большое количество методов факторизации, которые отличаются вычислительной сложностью.
Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел. В то же время доказано, что родственная задача о распознавании простоты числа является полиномиально разрешимой и для неё существует много эффективных тестов простоты.
Эти методы могут быть использованы в алгоритмах шифрования RSA, где вся секретная часть спрятана не в знании кода алгоритма, а в наличии ключа, длинного числа, подданного на «вход» алгоритма вместе с защищаемыми данными. Читать дальше >
