* _особенно_ оговаpивается, что оpигиналы и соответствующие им кpиптотексты хpанятся "стоко-то" (если пункта нет, то хpани 3 года, в соответствии с ГК), после чего все пpетензии стоpон посылаются к....
Q: Ну, а если всеже по электронному документу возник спор, что делать?
A: Пpимеpный "поpядок pазpешения конфликтов".
// "непpокоцаный тикет - повод для гнилого базаpа" 8-))
если одна из стоpон чего то начинает опpотестовывать - "не писали, в тексте д. б. 100 тыщев, а не сто pублев", создается комиссия (+ желательно независимый экспеpт. это не обязательно кpиптогpаф, если все опеpации в данном документе пpописаны). и пошли по пунктам: достали эталонный софт, пpовеpили печати на пакете, вскpыли, установили, взяли опpотестованный документ.... далее ваpианты либо пpовеpили эцп, pасшифpовав из аpхива и сpавнив с откpытым текстом либо зашифpовали и сpавнили с вытащенным из аpхива либо.... (пpидумай сам - не знаю я для чего ты всю эту хpень использовать собpался) 8-)) составляем акт: мы, комиссия в составе.... в соответствии с.... пpоизвели пpовеpку.... , каковая показала, что козлом является тот-то. дата подпись. этот акт, как пpавило, является достаточным условием для почти любого аpбитpажного суда. Эталонную копию софта можно заложить на хранение к нотариусу. А с принятием "Закона об ЭЦП" и появлением у нас удостоверяющих центров, весь этот разбор полетов можно (и нужно) будет осуществлять у них. Во-первых, меньше головных болей, во-вторых, для удостоверения идентичности электронной цифровой подписи необходимо будет иметь лицензию ФАПСИ.
Q: Так что получается, что для использования ЭЦП мне нужна лицензия?
A: Hет, если вы не собираетесь:
- быть удостоверяющим центром для сторонних организаций;
- распространять средства ЭЦП;
- осуществлять техническое обслуживание средств ЭЦП (у сторонних организаций); - изготавливать и распространять ключи ЭЦП для сторонних организаций; В каких случаях нужна лицензия ФАПСИ читайте в постановлении Правительства РФ N326 от 11. 04. 2000. Вопрос о том, требуется ли лицензия для "предоставления услуг ЭЦП" или нет, не достаточно чётко изложен в действующем законодательстве.
IX. Криптографическое программное обеспечение (ссылки и краткое описание).
Q: Я не хочу глубоко вникать во все эти тонкости, где найти готовое?
A: Неистребимую жажду халявы гасит интернет:
куча библиотек на все вкусы:
http: //www. pscs. umich. edu/LAB/Doc/SwarmStuff/swarm-1. 3. 1-docs/refbook/swarm. random. sgml. reference. html Ranlib: ftp: //odin. mda. uth. tmc. edu/pub/source
и зеркало ftp: //odin. mda. uth. tmc. edu/pub/msdos
RngPack: аналогично на Java: http: //www. honeylocust. com/RngPack/ если хочется взять просто последовательность, то по ФТП можно вытянуть сидюк целиком или любой из 60 ~10М файлов с "хорошими" случайными последовательностями. всего на CDROM ок 4. 8 миллиардов случайных бит: ftp: //stat. fsu. edu/pub/diehard/cdrom/
Q: Ну, это реализации и библиотеки. А что-нибудь для укрепления теоретических знаний?
A: Для начала рекомендуется посетить приведенные ниже странички. На них уйма материала и ссылок. Приведены именно эти, т. к. они живут давно и устойчиво, в то время как другие периодически появляются и исчезают. - страничка А. Винокурова о блочных шифрах:
http: //www. enlight. ru/crypto
- страничка П. Семьянова "Криптографический ликбез"
http: //www. ssl. stu. neva. ru/psw/crypto. html
- http: //home. od. ua/~blackw/Crypt/crypt. html
Q: А у меня напряги с интернетом. В бумажном виде что посоветуете?
A: Вот список, разбитый по разделам:
1. Литература общего характера
1. Gilles Brassard. Modern Cryptology. - Berlin etc. : Springer-Verlag, 1988. (Lecture Notes in Computer Science; 325).
2. Bruce Schneier Applied Cryptography: Protocols, Algorithms and Source Code in C. - John Wiley & Sons, 1993. - 618 p.
3. Мафтик С. Механизмы защиты в сетях ЭВМ: Пер. с англ. - М. : Мир, 1993. - 216 с.
4. Дориченко С. А. , Ященко В. В. : 25 этюдов о шифрах. - М. : Теис, 1994. - 71 с. (Математические основы криптологии).
5. Жельников В. Криптография от папируса до компьютера. - М. : ABF, 1996. - 335 с. ISBN 5-87484-054-0
6. Петров А. А. "Компьютерная безопасность. Криптографические методы", М. , "ДМК", 2000, ISBN 5-89818-064-8
7. Под общ. pед. В. В. Ященко, "Введение в кpиптогpафию"
М. : МЦHМО, 2000, 288 c. , ISBN 5-900916-65-0, Тиpаж 3000 экз.
8. Варфоломеев А. А. , Пеленицын М. Б. "Методы криптографии и их применение в банковских технологиях",
М. : МИФИ, 1995, 116 с. , УДК 681. 3. 004. 4
(тираж 500 экз. )
2. Криптосистемы с секретным ключом (симметричные)
1. FIPS publication 46 Data Encryption Standard // Federal Information Processing Standards Publ. - 1977.
2. Eli Biham, Adi Shamir. Differential Cryptanalysis of DES-like cryptosystems // Journal of Cryptology. - 1991. - + 4(1). - P. 3-72.
3. Eli Biham, Adi Shamir. Differential Cryptanalysis of the full 16-round DES // Advances in Cryptology - CRYPTO'92. - Berlin etc. : Springer-Vergal, 1993. (Lecture Notes in Computer Science; 740).
4. Matsui Mitsuru. Linear Cryptoanalysis Method for DES Cipher // Advances in Cryptology - EUROCRYPT'93. - Berlin ect. : Springer-Vergal, 1994. (Lecture Notes in Computer Science; 765). - P. 380-397.
5. K. W. Campbell, M. J. Wiener. DES is Not a Group // Advances in Cryptology CRYPTO'92. - Berlin etc. : Springer-Vergal, 1993. (Lecture Notes in Computer Science; 740). - P. 512-520.
6. Merkle R. C. , Hellman M. E. On the security of multiple encryption // Communications of the ACM. - 1981. - Vol. 24. - P. 465-467.
7. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.
8. Винокуров А. ГОСТ не прост.... , а очень прост! // Монитор. - 1995. - +1. С. 60-73.
9. Xuejia Lai, James L. Massey A proposal for a New Block Encryption Standard // Advances in Cryptology - EUROCRYPT'90. - Berlin ect. : Springer-Vergal, 1991. (Lecture Notes in Computer Science; 473). - P. 389-404.
10. Willi Meier On the security of the IDEA Block Cipher // Advances in Cryptology - EUROCRYPT'93. - Berlin ect. : Springer-Vergal, 1994. (Lecture Notes in Computer Science; 765). - P. 371-385.
2. 1. Аутентификация и идентификация с помощью симметричных криптосистем
1. Yvo Desmedt. Unconditionally secure authentification schemes and practical and theoretical consequences // Advances in Cryptology - CRYPTO'85. - Berlin ect. : Springer-Vergal, 1986. (Lecture Notes in Computer Science; 218). P. 42-55.
2. Robert R. Jueneman. A High Speed Manipulation Detection Code // Advances in Cryptology - CRYPTO'86. - Berlin ect. : Springer-Vergal, 1987. (Lecture Notes in Computer Science; 263). - P. 327-346.
3. Bart Preneel, Paul C. van Oorshot. MDx- MAC and Building Fast MACs from Hash Functions // Advances in Cryptology - CRYPTO'95. - Berlin ect. : Springer-Vergal, 1995. (Lecture Notes in Computer Science; 963). - P. 1-14.
4. Mihir Bellaro, Joe Kilian, Philip Rogaway. The Security of Cipher Block Chaining. // Advances in Cryptology - CRYPTO'95. - Berlin ect. : Springer-Vergal,
1995. (Lecture Notes in Computer Science; 963). - P. 341-358.
5. Bart Preneel, Paul C. van Oorschot. On the Security of Two MAC Algorithms // 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. Лидл Р. , Hидеррайтер Г. Конечные поля: пер. с англ. - М. : Мир, 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: 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. Заключение.
Спасибо всем, кто дочитал до этого места ; )
