- •11. Сжатие информации. Арифметическое кодирование
- •13 Алгоритм Евклида
- •14. Введение в теорию чисел. Функции Эйлера
- •15. Введение в теорию чисел. Модульная арфиметика
- •16. Введение в теорию чисел. Методы построения простых чисел.
- •17. Построение последовательностей псевдослучайных числа. Линейный конгруэнтный метод
- •18. Методы генерирования псевдослучайных чисел. Недостатки классических генераторов псевдослучайных чисел
- •19. Современные алгоритмы генерации псевдослучайных чисел.
- •21. Проверка статистических гипотез. Критерий Пирсона.
- •22. Статистическая оценка качества последовательностей псевдослучайных чисел. Тесты серий.
- •20. Проверка статистических гипотез. Общая схема.
- •26. Одноалфавитные и многоалфавитные шифры замены.
- •28. Механизация шифрования.
- •29.Потоковые шифрующие системы.
- •30.Стандартные системы шифрования. Алгоритм des.
- •32.Криптография с открытым ключом.
- •33. Криптография с открытым ключом. Алгоритм rsa
- •34.Криптография с открытым ключом. Алгоритм Диффи-Хеллмана.
- •35.Шифрование на базе эллиптических кривых.
- •36.Криптографические системы на базе эллип-тических кривых. Ана-лог rsa
- •37.Криптографические системы на базе эллип-тических кривых. Ана-лог алгоритма Диффи-Хеллмана.
- •38. Элементы теории сложности. Машина Тьюринга.
- •39. Элементы теории сложности. Функции вычислимые по Тьюрингу.
- •40. Защита программного обеспечения от обратного проектирования.
- •41.Запутывающие преобразования программ.
- •42.Алгоритмы разделения секрета
35.Шифрование на базе эллиптических кривых.
Криптография на основе эллиптических кривых дает преимущество перед RSA или Диффи – Хеллмана т.е обеспечивается эквивалентная зашита при меньшей длине ключа.
Эллиптические кривые и их свойства:
1)Любая вертикальная (параллельная оси Оу) прямая, не пересекает кривую ни разу или пересекает дважды.
2) Любая другая прямая пересекает кривую один или три раза. 3)Условимся точку касания считать за два пересечения.
Операции над точками эллип-тических кривых:
1)Операция сложения точек очевидным образом коммутативна: для любых точек Р, Q эллиптической кривой справедливо Р + Q = Q + Р. 2)В проективной геометрии доказывается ассоциативность операции сложения точек: для любых трех точек Р, Q, R эллиптической кривой справедливо (Р + Q) + R = P + (Q+R).
Построение множества точек эллиптическойкри-вой Ep(a,b):
1)Для каждого х , где 0<=x<=p, вычисляется Y = x^3 + ax + b (modp). 2)Для Y выясняется , имеет ли оно квадратный корень по модулю p. 3)Если “нет”, то в E(a,b) нет точек для такого х. 4)Если корень существует, то имеется 2 значения y,соответствующих операции извлечения квадратного корня. 5)Эти значения (x,y) и будут точками E(a,b). 6)Все значения вычисляются по модулю р, где р- простое число. 7)Элементами данной эллиптической кривой являются пары неотрицательных целых чисел, которые удовлетворяют частному виду эллиптической кривой : y^2=x^3+ax+b (modp). 8)Такую кривую обозначают E(a,b). 9)При этом числа a и b должны быть меньше p и удовлетворять условию 4*a^3+27*b^2(modp) неравном 0.
36.Криптографические системы на базе эллип-тических кривых. Ана-лог rsa
Эллиптические кривые и их свойства:
1)Любая вертикальная (параллельная оси Оу) прямая, не пересекает кривую ни разу или пересекает дважды.
2) Любая другая прямая пересекает кривую один или три раза.
3)Условимся точку касания считать за два пересечения.
Сопоставление шагов алгорит-ма RSA при работе в Zn и Ep(a,b)
1)Определение рабочего модуля(Алиса заранее выбирает два простых числа p и q и вычисляет произведение n =p*q).
2) Выработка открытого ключа(Алиса выбирает случйным образом открытый ключ е, 1<e<n и отправляет Бобу пару чисел(n,e)).
3)Выработка секретного ключа(Алиса вычисляет секретный ключ d, d=e^(-1) mod (p+1)(q+1) ).
4)Боб шифрует сообщение M , получая шифр – текст C , и отправляет его Алисе(С=e(M,y),где y-случайное число; (M,y)-точка эллиптической кривой).
5)Алиса расшифровывает шифр- текст C , восстанавливая исходное сообщение M, (M,y)=dC.
37.Криптографические системы на базе эллип-тических кривых. Ана-лог алгоритма Диффи-Хеллмана.
Эллиптические кривые и их свойства:
1)Любая вертикальная (параллельная оси Оу) прямая, не пересекает кривую ни разу или пересекает дважды.
2) Любая другая прямая пересекает кривую один или три раза.
3)Условимся точку касания считать за два пересечения.
Сопоставление шагов алгорит-маДиффи-Хеллмана при работе в Zn и Ep(a,b):
1)Определение рабочей группы GF(p)(рабочей кривой) базового элемента g (базовой точки).Алиса выбирает и отправляет Бобу эллиптическую кривую и случайную точку G на ней.
2)Алиса выбирает случайное число а и вычисляет и отправляет Бобу точку G(a)=aG.
3)Боб выбирает случайное число b и вычисляет и отправляет Алисе точку G(b)=bG.
4)Алиса вычисляет секретную точку K=aG(b).
5)Боб вычисляет секретную точку K=bG(a).
6)У Алисы и Боба получается один и тот же секретный элемент, потому что aG(b)=a(bG)=(ab)G=b(aG)=bG(a)
