Секция 3 из 3 - Предыдущая - Следующая
Все секции
- 1
- 2
- 3
// Advances in Cryptology - EUROCRYPT'96. - Berlin ect.: Springer-Vergal, 1996.
(Lecture Notes in Computer Science; 1070). - P. 19-32.
6. Metzger P., Simpson W. IP Authentication using Keyed MD5. - Network Working
Group. - RFC 1828. - August 1995.
7. Burt Kaliski, Matt Rodshaw. Message Authentication with MD5 // CryptoBytes.
- Spring 1995. - Vol. 1., No. 1. (The technical newsletter of RSA Laboratories,
a division of RSA Data Security, Inc).
8. Ronald Rivest. The MD5 Message-Digest Algorithm. - Network Working Group. -
RFC 1321.
9. Bert den Boer, Antoon Bosselaers. Collisions for the Compression Function
of MD5 // Advances in Cryptology - EUROCRYPT'93. - Berlin ect.:
Springer-Vergal,
1994. (Lecture Notes in Computer Science; 765).
10. Hans Dobbertin. Cryptanalysis of MD5 Compress.
11. Hans Dobbertin. The Status of MD5 After a Recent Attack // CryptoBytes. -
Spring 1996. - Vol. 2., No. 2. (The technical newsletter of RSA Laboratories, a
division of RSA Data Security, Inc). P. 1-6.
12. NIST FIPS PUB 180-1. Secure Hash Standard. - National Institute of
Standards and Technology, US Department of Commerce. - 17 Apr 1995.
13. Martin Abadi, Roger Needham. Prudent Engineering Practice for Cryptographic
Protocols. - June 1, 1994. - 31 p. - (Rep. DEC Systems Research Center, No.
125).
3. Криптосистемы с открытым ключом (асимметричные)
1. Терехов А.H., Тискин А.В. Криптография с открытым ключом: от теории к
стандарту // Программирование. - 1994. - + 5. - Р. 17-22.
2. IEEE P1363: Standard for Public-Key Cryptography (Working Draft).
3. А. Саломаа "Криптография с открытым ключом",
М., МИР, 1996, ISBN 5-03-0011991-X
3.1. Алгебраические основы
1. Виноградов И.М. Основы теории чисел. - М., 1949. - 180 с.
2. Дональд Кнут. Искусство программирования для ЭВМ. Т. 2. Получисленные
алгоритмы: пер. с англ. - М., Мир, 1977. - 724 с.
3. Лидл Р., Нидеррайтер Г. Конечные поля: пер. с англ. - М.: Мир, 1988. - в
2-х т.
4. Ахритас А. Основы компьютерной алгебры с приложениями: пер. с англ. - М.:
Мир, 1994. - 544 с.
5. Victor S. Miller. Use of Elliptic Curves in Cryptography // Advances in
Cryptology - CRYPTO'85. - Berlin etc.: Springer-Verlag , 1986. (Lecture Notes
in
Computer Science; 218). - P. 417-426.
6. Alfred Menezes. Elliptic Curve Public Key Cryptosystems. - Boston: Kluwer
Academic Publishers - 1993.
7. Alfred Menezes. Elliptic Curve Cryptosystems. // CryptoBytes. - Spring
1995. - Vol. 1., No. 2. (The technical newsletter of RSA Laboratories, a
division of RSA Data Security, Inc). P. 1-4.
8. Т.Кормен, Ч.Лейзерсон, Р.Ривест "Алгоритмы. Построение и анализ",
М., МЦНМО, 1999, ISBN 5-900916-37-5
9. Нечаев В.И. "Элементы криптографии (Основы теории защиты информации)",
М.: Высш. шк., 1999. - 109 с. ISBN 5-06-003644-8
3.2. Односторонние функции
1. Erich Bach. Intractable Problems in Number Theory // Advances in Cryptology
- CRYPTO'88. - Berlin etc.: Springer-Vergal, 1989. (Lecture Notes in Computer
Science; 403). - P. 77-93.
2. Andrew M. Odlyzko. The Future of Integer Factorization // CryptoBytes -
Summer 1995. - Vol. 1., No. 2. (The technical newsletter of RSA Laboratories, a
division of RSA Data Security, Inc). - P. 5-12.
3. Pohlig S, Hellman M.E. An improved algorithm for computing logarithms over
GF(p) and its cryptographic significance // IEEE Trans. on Information Theory.
- 1978. - vol. IT - 24. - P. 106-110.
4. Andrew M. Odlyzko. Discrete Logarithms in Finite Fields and their
Cryptographic Significance // Advances in Cryptology - EUROCRYPT'84. - Berlin
etc.: Springer-Vergal, 1985. (Lecture Notes in Computer Science; 209). - P.
224-314.
5. Benny Chor, Oded Goldeich. RSA/Rabin least significant bits are
1/2+1/(poly(log n)) secure // Advances in Cryptology - CRYPTO'84. - Berlin
etc.:
Springer-Vergal, 1985. (Lecture Notes in Computer Science; 196). - P. 303-313.
6. Benny Chor, Oded Goldeich, Shafi Goldwasser. The Bit Security of Modular
Squaring given Partial Factorization of the Modulos // Advances in Cryptology -
CRYPTO'85. - Berlin etc.: Springer-Vergal, 1986.
(Lecture Notes in Computer Science; 218). - P. 448-457.
3.3. Асимметричные криптосистемы
1. Diffie W., Hellman M.E. New directions in cryptography // IEEE Trans. on
Information Theory. - 1976. - vol. IT -22. - P. 644-654.
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: Ну зачем сразу читать 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.
На страничке Санкт-Петербургского Технического Университета
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:
Читай книжки. Я видел описания тестов на простоту, например, в
ИНТ. Современные проблемы математики.Фундаментальные направления. Т. 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. Заключение.
Спасибо всем, кто дочитал до этого места ;)
Секция 3 из 3 - Предыдущая - Следующая
© faqs.org.ru
