2. Bert den Boer. Diffie-Hellman is as Strong as Discrete Log for Certain Primes // Advances in Cryptology - CRYPTO'88. - Berlin etc. : Springer-Verlag, 1989. (Lecture Notes in Computer Science; 403). - P. 530-539.
3. Ueli M. Maurer Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms // Advances in Cryptology CRYPTO'94. - Berlin etc. : Springer-Verlag, 1995. (Lecture Notes in Computer Science; 839). - P. 271-281.
4. Ronald L. Rivest, Adi Shamir, Leonard Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems // Communications of the ACM. 1978. - Vol. 21, No. 2- P. 120-126.
5. Johan Hastad. Using RSA with low exponent in a public key network // Advances in Cryptology - CRYPTO'85. - Berlin etc. : Springer-Verlag, 1986. (Lecture Notes in Computer Science; 218). - P. 403-408.
6. Don Coppersmith, Matthew Franklin, Jacques Patarin, Michael Reiter. Low-Exponent RSA with Related Message // Advances in Cryptology - EUROCRYPT'96. - Berlin etc. : Springer-Verlag, 1996. (Lecture Notes in Computer Science; 1070). - P. 1-9.
7. Taher El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // IEEE Trans. on Inform. Theory. - July 1985. - vol. IT -31, No. 4. - P. 469-472.
8. Taher El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // Advances in Cryptology - CRYPTO'84. - Berlin etc. : Springer-Verlag, 1985. (Lecture Notes in Computer Science; 196). - P. 10-18. 3. 4. Цифровая подпись
1. Ross Anderson, Roger Needham. Programming Satan's Computer // (Lecture Notes in Computer Science; 1000).
2. Daniel Bleichenbacher. Generating ElGamal Signatures Without Knowing the Secret Key // Advances in Cryptology - EUROCRYPT'96. - Berlin etc. : Springer-Verlag, 1996. (Lecture Notes in Computer Science; 1070). - P. 10-18.
3. FIPS PUB 186, Digital Signature Standard (DSS). - National Institute of Standards and Technology, US Department of Commerce. - 19 May 1994.
4. Gustavus J. Simmons. Subliminal Communication is Easy Using the DSA // Advances in Cryptology - EUROCRYPT'93. - Berlin etc. : Springer-Verlag, 1994. (Lecture Notes in Computer Science; 765). - P. 218-232.
5. ГОСТ Р 34. 10-94. Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма. - Введ. 01. 01. 95. - М. : Изд-во стандартов, 1994
6. Birgitt Pfotzmann. Digital Signature Schemes. General Framework and Fail-Stop Signatures. - Berlin etc. : Springer-Verlag, 1990. (Lecture Notes in Computer Science; 1100). - P. 396.
7. David Chaum, Hans van Antwerpen. Undeniable Signatures // Advances in Cryptology - CRYPTO'89. - Berlin etc. : Springer-Verlag, 1990. (Lecture Notes in Computer Science; 435). - P. 212-216.
8. David Chaum. Zero-Knowledge Undeniable Signatures // Advances in Cryptology - EUROCRYPT'90. - Berlin etc. : Springer-Verlag, 1991. (Lecture Notes in Computer Science; 473). - P. 458-464.
9. Amos Fiat, Adi Shamir. How to prove yourself: Practical Solutions to Identification and Signature Problems // Advances in Cryptology - CRYPTO'86. Berlin etc. : Springer-Verlag, 1987. (Lecture Notes in Computer Science; 263). P. 186-194.
10. Uriel Feige, Amos Fiat, Adi Shamir. Zero Knowledge Proofs of Identity // Proc. 19th Annual ACM Symp. on Theory of Computing. - 1987. - P. 210-217.
11. Uriel Feige, Amos Fiat, Adi Shamir. Zero Knowledge Proofs of Identity // Journal of Cryptology. - Vol. 1, No. 2. - 1988. - P. 77-94.
12. Silvio Micali, Adi Shamir. An Improvement of the Fiat-Shamir Identification and Signature Scheme // Advances in Cryptology - CRYPTO'88. - Berlin etc. : Springer-Verlag, 1989. (Lecture Notes in Computer Science; 403). - P. 216-231.
13. Schnorr C. P. Efficient Identification and Signatures for Smart Cards // Advances in Cryptology - CRYPTO'89. - Berlin etc. : Springer-Verlag, 1990. (Lecture Notes in Computer Science; 435). - P. 239-251. ================================================
Q: А что есть стандартного в области криптографии в Windows?
A: Криптографические функции есть начиная с Win95 osr 2, WinNT 4. 0. В частности функция зашифрования называется CryptEncrypt(a, w), а расшифрования CryptDecrypt(a, w).
Q: Где взять более подробное описание (прототипы функций) и что там используется ?
A: Как обычно - берешь Win32 API.... Алгоpитмы могyт быть любыми, поcколькy cиcтема pаcшиpяемая и позволяет подключение дополнительных кpиптопpовайдеpов. Cтандаpтный кpиптопpовайдеp, входящий в cоcтав Win* иcпользyет RSA для обмена ключами и ЭЦП, RC2 и RC4 для шифpования и MD5 и SHA для хэшиpования. Описание констант и функций, например, в wincrypt. h от C++ Builder-а 3. 0. Алгоритм-это преимущественно RSA или сделанный на ее платформе. Provider Type Key Exchange Signature Encryption Hashing
PROV_RSA_FULL RSA RSA RC2, RC4 MD5, SHA PROV_RSA_SIG n/a RSA n/a MD5, SHA PROV_DSS n/a DSS n/a SHA PROV_FORTEZZA KEA DSS Skipjack SHA PROV_MS_EXCHANGE RSA RSA CAST MD5 PROV_SSL RSA RSA varies varies
A2: Hу зачем сразу читать header-ы (их потом), есть нормальная документация: Сообщения и сертификаты:
http: //msdn. microsoft. com/library/psdk/crypto/cryptovrvw_8395. htm Аутентификация и шифрование соединений:
http: //msdn. microsoft. com/library/psdk/secpack/secpacknavpage_0o1f. htm Обзор системы на русском:
http: //www. microsoft. com/rus/windows2000/library/security/ X. ПРИЛОЖЕНИЯ. Примеры реализации.
Первоначальная мысль вставить это сюда была критически обдумана и отброшена слишком большой объем. Вместо этого решено было создать библиотеку реализаций и сложить в одном месте в инете. Пока это место находится по адресу: ftp: //ftp. wtc-ural. ru/pub/ru. crypt
XI. Здесь пары вопрос/ответ, которые я затруднился определить в какой-либо раздел. Вобщем, "разное" : )
Q: Как проверить "случайность" моего ГСП (генератор случайной последовательности).
A1: В интеpнете есть "Diehard test battery". Этот комплект содеpжит 15 тестов чисел на случайность. Адpес http: //stat. fsu. edu/~geo/diehard. html A2:
Предположим у тебя имеется файл (массив, набор чисел) значений некоторой случайной величины и ставится задача изучения ее свойств, т. е. являются ли эти значения равномерно распределенными (равновероятными) в некотором интервале.
Относительно изучаемой случайной величины можно сделать два предположения, называемых нуль-гипотезой и альтернативной гипотезой:
1) Случайная величина имеет равномерное распределение (нуль-гипотеза) 2) Случайная величина не имеет равномерного распределения, т. е. закон распределения случайной имеет уклонения от равномерного распределения (альтернативная гипотеза).
В математической статистике сущесвуют ряд тестов, назваемых критериями согласия для проверки функции распределения случайной величины на предмет ее соответствия теоретически ожидаемому закону распределения. Примерами таких критериев согласия являются Хи-квадрат (критерий Пирсона) и критерий Kолмогорова-Смирнова, критерий серий и т. д. Kритериев много. Статистические критерии могут установить только отличие теоретического и экспериментального распределений, поэтому нуль-гипотеза, как правило выдвигается для проверки - нет ли оснований для ее отбрасывания. Другими словами невозможно доказать "чистую случайность" последовательности, но можно с определенной степенью вероятности опровергнуть противоположное утверждение. Таким образом, для решения является ли различие достоверным необходимо установить границы для близости-различия частот в выборке и теоретически ожидаемых частот. Данная величина называется уровнем значимости, и обычно принимает значения 5%, 1%, 0. 1%. Результат называется значимым на уровне 5%, если правильная нуль-гипотеза будет отклонена не более, чем в 5% случаев. Kритерий согласия Хи-квадрат.
Пусть необходимо протестировать генератор, выдающий некоторую последовательность бит, относительно которой выдвигается нуль-гипотеза о том, что эта последовательность имеет равномерное распределение. Обозначим объем выборки n. Пусть мы сгенерировали 100 бит, тогда n=100. Пусть выборка разделена на k классов. Если, например, исследуем частоты появления только 0 и 1 - тогда количество классов два. Пусть В_i наблюдаемая частота=количество появлений некоторого признака в выборке. Обозначим В_0 - количество нулей, В_1 - количество единиц. Пусть E_i - ожидаемая частота признака i. Для нашего случая E_0=E_1= 0. 5*n. Формула Хи-квадрат для вычисления различия между экспериментальным и теоретическим распределениями следующая: i=k-1 ____ 2 \ (В_i - Е_i) Хи-квадрат = /___ ------------ i=0 Е
Для численного анализа вводится понятие "степеней свободы" K=(k-1).
В результате обработки экспериментальных данных получаем два числа: Хи-квадрат и K. Выберем уровень значимости=вероятность ошибки, напрмер 0. 1% Открываем справочник (учебник) по мат. статистике или терии вероятностей и находим таблицу 5%, 1% и 0. 1% границ для Хи-квадрат. Если значение Хи-квадрат меньше или равно табличному, то нуль-гипотеза принимается. Иначе - отклоняется.
Если для заданного количества степеней свободы найти в таблице вычисленное значение Хи-квадрат, то можно узнать уровень значимости=вероятность ошибки.
Чтобы получить польше подтверждений о качестве генератора, тесты необходимо прогнать для разных значений k, т. е применить изложенный теоретический материал к случайным величинам вида - 00, 01, 10, 11 E_i=0. 25 = 1/(2^2) - 000, 001, 010 .... E_i=0. 125 = 1/(2^3) - 0000, 0001, E_i= 1/(2^4) и т. д
Чем больше тестов, тем больше вероятностей отбросить сомнения.
>Ограничение: для использования критерия согласия Хи-квадрат выборка должна быть не слишком малой ! т. е. (n >= 40) и ожидаемые частоты должны быть не менее 5 (Е_i >= 5). Если они меньше, то их необходимо увеличить до требуемого уровня путем объединения соседних классов. Kритерий согласия Kолмогорова-Смирнова (K-С)
назначение - аналогично предыдущему. Проверяется гипотеза- выборка относится к равномерному распределению. Определяют значения Е и В и образуют функцию накопленной частоты F_e и F_b, находят максимум разности и делят на объем выборки n. max | F_b - F_e | K-С = -------------------- n Таблица уровня значимости: 5% 1. 36 * Kорень_из(n) 1% 1. 63 * Kорень_из(n)
Если вычисленное значение K-С меньше или равно соотвю уровня значимости, то нуль-гипотеза принимается, иначе отклоняется. Ограничения объем выборки n>35.
Hа страничке Санкт-Петербургского Технического Университета http: //www. ssl. stu. neva. ru/psw/crypto. html
имеется книга "Поточные шифры. Результаты заруюежной открытой криптологии" (автор неизвестен). Глава 3 называется "Статистические свойства и меры сложности последовательностей" (стр. 35-43). В этой главе описаны: - Частотный тест - Последовательный тест - Тест серий - Автокорреляционный тест - Универсальный тест - Тест повторений - Сравнение тестов l-грамм - Kомбинирование тестов - отсечение слабых последовательностей.
Из общематематической литературы можно посоветовать практически любую книгу по математической статистике, например А. А. Боровков "Теория вероятностей и мат. статистка", Закс "Статистическое оценивание". Q: Как проверить число на простоту? A1:
Вот к чему привели различные поиски. Для общего случая простых чисел существует по крайней мере два алгоритма проверки их простоты (естественно не считая всяких там переборов в лоб). Jacobi sum test (точнее APR-CL (Adleman, Pomerance and Rumely; Cohen and Lenstra), по имени ученых, которые предложили и развили алгоритм) и ECPP (Elliptic Curve Primality Test). По времени выполнения они приблизительно одинаковые, но ECPP имеет то преимущество, что оно создает
некий сертификат, используя который можно в любой момент проверить простое числоили нет в сравнительно короткое время. (на васике)
http: //archives. math. utk. edu/software/msdos/number. theory/ubasic/. html В него входит программы aprt-cle. ub, это APR-CL. (на С) А вот ECPP:
http: //www. lix. polytechnique. fr/~morain/Prgms/ecpp. english. html A2:
Читай книжки. Я видел описания тестов на простоту, например, в
ИHТ. Современные проблемы математики. Фундаментальные направления. Т. 49. 1990. с. 63
Алгебра и теория чисел (с приложениями): Избранные доклады семинара H. Бурбаки: Сб. статей 1976-1985 гг. Пер. с англ. и франц. - М. Мир, 1987. с. 47 В первой описаны следующие алгоритмы: 1) Факторизация Ферма 2) Вероятностный алгоритм CLASNO 3) Алгоритм Шенкса SQUFOF 4) Метод непрерывных дробей CFRAC 5) (p-1)-метод Полларда 6) Метод эллиптических кривых Во второй упор сделан на Adleman-Pomerance-Rumely. а вот еще:
Riesel H. Prime numbers and computer methods for factorization // Progr. Math. 57. - Birkhaser: Boston, 1985. - 464 c. статья "A Tale of Two Sieves" на:
http: //www. ams. org/publications/notices/199612/pomerance. html Обзорные статьи (списочек от Alexander Krotoff): Williams H. C. Primality testing on a computer, Arts Combin. 5(1978). 127-185.
Lenstra H. W. Jr. Primlity testing algotitms after Adleman, Rumely and Williams. Seminare Bourbaki, 34-e annee, 1980/1981 #576, 1-15.
Простейший алгоритм на уcиленной малой теореме Ферма имеет сложность O(ln(n)^2). Основан на гипотезе Римана. Solovay R. Strassen V.
A fast Monte-Carlo test for primality, SIAM J. Comput. 6(1977), 84-85, 7(1978), 118
Adleman L. M. On distinguishing prime numbers from composite numbers (abstract) Proc 21st Annual IEEE Symposium on Foundation of Science (1980) 387-406. Adleman L. M. , Pomerance C. Rumely R. S. On distiguishig prime numbers from composite numbers, Ann. of Math. 117(1983) 173-206 Сложность алгоритма O(ln(n)^{C*ln(ln(ln(n)))})
Pollard J. M. Theorems on factorization and primality testing, Proc. Cambrdge Philos. Soc. 76(1974), 521-528 сложность O(n^(1/8)).
Q: Я тут написал программу и хочу построить уникальный ключ, привязав его к "железу", номеру материнки, процессора, жесткого диска, сетевой карте. К чему лучше?
A: Ни к чему. Привязка к "железу" (любому) неэффективна в случае, если комп взят из "большой китайской партии" и неудобна в
использовании, поскольку апгрейд "железа" явление достаточно частое, чтобы при сколь-нибудь серьезном тираже программы ты поимел много забот с поддержкой. Q: Что такое необратимое шифрование?
A: Такого термина нет. Шифрование по определению обратимо, иначе это действие бессмысленно. Обычно используется понятие хэш (свертка). См. раздел "хэш-функции".
Q: А возможно ли создание аpхиватоpа у котоpого будет коэффициент сжатия 1 к миллиону?
A: Согласно Шеннону, если некотоpый источник инфоpмации способен генеpиpовать N pазличных символов S_1, S_2, .... , S_N с
веpоятностями p_1, p_2, .... , p_N, то количество инфоpмации, поступающее с отдельным символом (т. е. теоpетически минимальное число бит, котоpое пpидется в сpеднем затpатить на кодиpование отдельного символа) составляет: I = - \sum_{i=1}^{N} {p_i * log_2 p_i}
(минус сумма пpоизведений веpоятности возникновения i-го символа на логаpифм по основанию два от этой же веpоятности).
Эта функция достигает максимума в случае, если все веpоятности p_i pавны между собой, и меньше во всех остальных случаях (наименьшее значение - 0, достигается тогда, когда веpоятность возникновения одного из символов pавна 1, а веpоятностивсех остальных pавны нулю).
Следствие 1: если способ кодиpования и статистические хаpактеpистики входного потока данных таковы, что в пpинципе допускают сжатие 1: 1000000, то любой "пpавильный" аpхиватоp для данного входного потока обеспечит близкий к этому значению коэффициент сжатия.
Следствие 2: если входной поток пpедставляет собой множество pеализаций pавномеpно pаспpеделенной случайной величины,
пpедставленных в pавномеpном безызбыточном коде (а такой, видимо, обычно и получается после опеpации шифpования), то не существует аpхиватоpа, обеспечивающего хоть какое-нибудь сжатие подобного потока. Q: Я, CrYpToGrAf....
A: В этой эхе за никами прятаться не принято. разве, что Disturbo (его и так все знают), а Harry Вush - это имя такое 8-)) Q: Дайте описание файла .... (MP3, JPG, etc)
A: Ребята, возьмите в интернете. Что любопытно, там описаны и заголовки, из которых можно почерпнуть "открытые тексты" для "частично" "plain-text known attack" XII. Заключение. Спасибо всем, кто дочитал до этого места ; )
Страницы: 1, 2, 3, 4, 5, 6, 7
