Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Поддерживать
www.wikidata.ru-ru.nina.az

Криптографически стойкий генератор псевдослучайных чисел англ Cryptographically secure pseudorandom number generator CSP

Криптографически стойкий генератор псевдослучайных чисел

Криптографически стойкий генератор псевдослучайных чисел (англ. Cryptographically secure pseudorandom number generator, CSPRNG) — это генератор псевдослучайных чисел с определёнными свойствами, позволяющими использовать его в криптографии.

Многие прикладные задачи криптографии требуют случайных чисел, например:

Задача

Требуемое «качество» случайности меняется от задачи к задаче. Например, генерация одного случайного числа в некоторых протоколах требует только уникальности, тогда как генерация мастер-ключа или одноразового шифроблокнота требует высокой энтропии. В идеале, генерация случайных чисел в КСГПСЧ использует высоконадёжный (источник энтропии), которым может быть (аппаратный генератор случайных чисел) или ход непредсказуемых процессов в системе — хотя в обоих случаях возможны неожиданные уязвимости. С точки зрения теории информации количество случайности — энтропия, которая может быть получена, равна энтропии, предоставляемой системой. Но зачастую в реальных ситуация требуется больше случайных чисел, чем можно получить при существующей энтропии. К тому же процедура получения случайности из самой системы требует достаточно много ресурсов (памяти и времени). В таких случаях, оправданно использование КСГПСЧ — это позволяет «растянуть» имеющуюся энтропию на большее число бит. Когда вся энтропия доступна до выполнения криптографического алгоритма, получается (потоковый шифр). Однако некоторые (криптосистемы) позволяют добавлять энтропию по мере работы, в таком случае алгоритм не является эквивалентом потокового шифра и не может использоваться в этом качестве. Таким образом, разработка потоковых шифров и КСГПСЧ тесно связаны.

Требования

Требования к обычному генератору псевдослучайных чисел выполняются и криптографически стойким ГПСЧ, обратное неверно. Требования к КСГПСЧ можно разделить на две группы: во-первых, они должны проходить статистические тесты на случайность; а во-вторых, они должны сохранять непредсказуемость, даже если часть их исходного или текущего состояния становится известна криптоаналитику. А именно:

  • КСГПСЧ должен удовлетворять «(тесту на следующий бит)». Смысл теста в следующем: не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать (k+1)-ый бит с вероятностью более 50 %. (Эндрю Яо) доказал в 1982 году, что генератор, прошедший «тест на следующий бит», пройдёт и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.
  • КСГПСЧ должен оставаться надёжным даже в случае, когда часть или все его состояния стали известны (или были корректно вычислены). Это значит, что не должно быть возможности получить случайную последовательность, созданную генератором, предшествующую получению этого знания криптоаналитиком. Кроме того, если во время работы используется дополнительная энтропия, попытка использовать знание о входных данных должна быть вычислительно невозможна.
    Пример
    Пусть генератор основывается на выводе битов двоичного представления числа π, начиная с какой-то неизвестной точки. Такой генератор, возможно, и пройдёт «тест на следующий бит», так как π, видимо, является случайной последовательностью (это было бы гарантированно, если доказать, что π является (нормальным числом)). Однако этот подход не является криптографически надёжным — если криптоаналитик определит, какой бит числа π используется в данный момент, он сможет вычислить и все предшествующие биты.

Большинство генераторов псевдослучайных чисел не подходит для использования в качестве КСГПСЧ по обоим критериям. Во-первых, несмотря на то, что многие ГПСЧ выдают последовательность, случайную с точки зрения разнообразных статистических тестов, они не надёжны по отношению к обратной разработке. Могут быть обнаружены специализированные, особым образом настроенные тесты, которые покажут, что случайные числа, получаемые из ГПСЧ не являются по настоящему случайными. Во-вторых, для большинства ГПСЧ возможно вычислить всю псевдослучайную последовательность, если их состояние скомпрометировано, что позволит криптоаналитику получить доступ не только к будущим сообщениям, но и ко всем предыдущим. КСГПСЧ разрабатываются с учётом сопротивляемости к различным видам криптоанализа.

Реализации

Рассмотрим три класса реализации КСГПСЧ:

  1. На основе криптографических алгоритмов
  2. На основе вычислительно сложных математических задач
  3. Специальные реализации

В последних часто используются дополнительные источники энтропии, поэтому, строго говоря, они не являются «чистыми» генераторами, так как их выход не полностью определяется исходным состоянием. Это позволяет дополнительно защититься от атак, направленных на определение исходного состояния.

Реализации на основе криптографических алгоритмов

  • Безопасный блочный шифр можно преобразовать в КСГПСЧ, запустив его в . Таким образом, выбрав случайный ключ, можно получать следующий случайный блок, применяя алгоритм к последовательным натуральным числам. Счет можно начинать с произвольного натурального числа. Очевидно, что периодом будет не больше, чем 2n для n-битного блочного шифра. Также очевидно, что безопасность такой схемы полностью зависит от секретности ключа.
  • Криптографически стойкая хеш-функция также может быть преобразована в КСГПСЧ. В таком случае исходное значение счетчика должно оставаться в секрете. Однако, некоторые авторы предостерегают от такого использования хеш-функций.
  • Большинство (потоковых шифров) работает на основе генерации псевдослучайного потока бит, которые некоторым образом комбинируется (почти всегда с помощью операции XOR) с битами открытого текста. Запуск такого шифра на последовательности натуральных чисел даст новую псевдослучайную последовательность, возможно, даже с более длинным периодом. Такой метод безопасен только если в самом потоковом шифре используется надёжный КСГПСЧ (что не всегда так). Опять же, начальное состояние счётчика должно оставаться секретным.

Реализации на основе математических задач

Специальные реализации

Существует целый ряд практически используемых ГПСЧ которые разрабатывались с учетом криптографической стойкости, например

  • (Алгоритм Ярроу) (англ. Yarrow algorithm) который пытается определить энтропию входных данных. Он используется в FreeBSD, (OpenBSD) и Mac OS X
  • (Алгоритм Fortuna) (англ. Fortuna algorithm), наследник алгоритма Ярроу.
  • Специальный файл ОС UNIX , в частности, /dev/urandom, реализованный в Linux.
  • Функция (CryptGenRandom) предоставленная в (CryptoAPI) компании Microsoft
  • (ISAAC) базируется на варианте (RC4).

Примечания

  1. Zvi Gutterman. Open to Attack: Vulnerabilities of the Linux Random Number Generator (англ.). Дата обращения: 15 ноября 2010. 27 февраля 2011 года.
  2. Stealthy Dopant-Level Hardware Trojans от 5 декабря 2013 на Wayback Machine (о потенциальном внедрении троянов в состав аппаратного генератора случайных чисел).
  3. Шнайер Б. 16 Генераторы псевдослучайных последовательностей и потоковые шифры // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — .
  4. Шнайер Б. 2.8 Генерация случайных и псевдослучайных последовательностей // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — .
  5. Peter Gutmann. Software Generation of Practically Strong Random Numbers (англ.) // Proceedings of the 7th USENIX Security Symposium : journal. — 1998. Архивировано 4 июля 2012 года.
  6. Adam Young, Moti Yung. Malicious Cryptography: Exposing Cryptovirology (англ.). — sect 3.2: , 2004. — P. 416. — . 27 мая 2009 года.
  7. Yarrow. Дата обращения: 15 ноября 2010. 8 ноября 2012 года.
  8. Описание функции CryptoGenRandom на MSDN (англ.). Microsoft. Дата обращения: 15 ноября 2010. Архивировано 4 июля 2012 года.

Ссылки

Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер

Дата публикации:
Kriptograficheski stojkij generator psevdosluchajnyh chisel angl Cryptographically secure pseudorandom number generator CSPRNG eto generator psevdosluchajnyh chisel s opredelyonnymi svojstvami pozvolyayushimi ispolzovat ego v kriptografii Mnogie prikladnye zadachi kriptografii trebuyut sluchajnyh chisel naprimer Generaciya klyuchej Odnorazovye sluchajnye chisla angl Nonces Odnorazovye shifrobloknoty Sol v shemah cifrovoj podpisi naprimer ECDSAZadachaTrebuemoe kachestvo sluchajnosti menyaetsya ot zadachi k zadache Naprimer generaciya odnogo sluchajnogo chisla v nekotoryh protokolah trebuet tolko unikalnosti togda kak generaciya master klyucha ili odnorazovogo shifrobloknota trebuet vysokoj entropii V ideale generaciya sluchajnyh chisel v KSGPSCh ispolzuet vysokonadyozhnyj istochnik entropii kotorym mozhet byt apparatnyj generator sluchajnyh chisel ili hod nepredskazuemyh processov v sisteme hotya v oboih sluchayah vozmozhny neozhidannye uyazvimosti S tochki zreniya teorii informacii kolichestvo sluchajnosti entropiya kotoraya mozhet byt poluchena ravna entropii predostavlyaemoj sistemoj No zachastuyu v realnyh situaciya trebuetsya bolshe sluchajnyh chisel chem mozhno poluchit pri sushestvuyushej entropii K tomu zhe procedura polucheniya sluchajnosti iz samoj sistemy trebuet dostatochno mnogo resursov pamyati i vremeni V takih sluchayah opravdanno ispolzovanie KSGPSCh eto pozvolyaet rastyanut imeyushuyusya entropiyu na bolshee chislo bit Kogda vsya entropiya dostupna do vypolneniya kriptograficheskogo algoritma poluchaetsya potokovyj shifr Odnako nekotorye kriptosistemy pozvolyayut dobavlyat entropiyu po mere raboty v takom sluchae algoritm ne yavlyaetsya ekvivalentom potokovogo shifra i ne mozhet ispolzovatsya v etom kachestve Takim obrazom razrabotka potokovyh shifrov i KSGPSCh tesno svyazany TrebovaniyaTrebovaniya k obychnomu generatoru psevdosluchajnyh chisel vypolnyayutsya i kriptograficheski stojkim GPSCh obratnoe neverno Trebovaniya k KSGPSCh mozhno razdelit na dve gruppy vo pervyh oni dolzhny prohodit statisticheskie testy na sluchajnost a vo vtoryh oni dolzhny sohranyat nepredskazuemost dazhe esli chast ih ishodnogo ili tekushego sostoyaniya stanovitsya izvestna kriptoanalitiku A imenno KSGPSCh dolzhen udovletvoryat testu na sleduyushij bit Smysl testa v sleduyushem ne dolzhno sushestvovat polinomialnogo algoritma kotoryj znaya pervye k bitov sluchajnoj posledovatelnosti smozhet predskazat k 1 yj bit s veroyatnostyu bolee 50 Endryu Yao dokazal v 1982 godu chto generator proshedshij test na sleduyushij bit projdyot i lyubye drugie statisticheskie testy na sluchajnost vypolnimye za polinomialnoe vremya KSGPSCh dolzhen ostavatsya nadyozhnym dazhe v sluchae kogda chast ili vse ego sostoyaniya stali izvestny ili byli korrektno vychisleny Eto znachit chto ne dolzhno byt vozmozhnosti poluchit sluchajnuyu posledovatelnost sozdannuyu generatorom predshestvuyushuyu polucheniyu etogo znaniya kriptoanalitikom Krome togo esli vo vremya raboty ispolzuetsya dopolnitelnaya entropiya popytka ispolzovat znanie o vhodnyh dannyh dolzhna byt vychislitelno nevozmozhna Primer Pust generator osnovyvaetsya na vyvode bitov dvoichnogo predstavleniya chisla p nachinaya s kakoj to neizvestnoj tochki Takoj generator vozmozhno i projdyot test na sleduyushij bit tak kak p vidimo yavlyaetsya sluchajnoj posledovatelnostyu eto bylo by garantirovanno esli dokazat chto p yavlyaetsya normalnym chislom Odnako etot podhod ne yavlyaetsya kriptograficheski nadyozhnym esli kriptoanalitik opredelit kakoj bit chisla p ispolzuetsya v dannyj moment on smozhet vychislit i vse predshestvuyushie bity Bolshinstvo generatorov psevdosluchajnyh chisel ne podhodit dlya ispolzovaniya v kachestve KSGPSCh po oboim kriteriyam Vo pervyh nesmotrya na to chto mnogie GPSCh vydayut posledovatelnost sluchajnuyu s tochki zreniya raznoobraznyh statisticheskih testov oni ne nadyozhny po otnosheniyu k obratnoj razrabotke Mogut byt obnaruzheny specializirovannye osobym obrazom nastroennye testy kotorye pokazhut chto sluchajnye chisla poluchaemye iz GPSCh ne yavlyayutsya po nastoyashemu sluchajnymi Vo vtoryh dlya bolshinstva GPSCh vozmozhno vychislit vsyu psevdosluchajnuyu posledovatelnost esli ih sostoyanie skomprometirovano chto pozvolit kriptoanalitiku poluchit dostup ne tolko k budushim soobsheniyam no i ko vsem predydushim KSGPSCh razrabatyvayutsya s uchyotom soprotivlyaemosti k razlichnym vidam kriptoanaliza RealizaciiRassmotrim tri klassa realizacii KSGPSCh Na osnove kriptograficheskih algoritmov Na osnove vychislitelno slozhnyh matematicheskih zadach Specialnye realizacii V poslednih chasto ispolzuyutsya dopolnitelnye istochniki entropii poetomu strogo govorya oni ne yavlyayutsya chistymi generatorami tak kak ih vyhod ne polnostyu opredelyaetsya ishodnym sostoyaniem Eto pozvolyaet dopolnitelno zashititsya ot atak napravlennyh na opredelenie ishodnogo sostoyaniya Realizacii na osnove kriptograficheskih algoritmov Bezopasnyj blochnyj shifr mozhno preobrazovat v KSGPSCh zapustiv ego v rezhime schetchika Takim obrazom vybrav sluchajnyj klyuch mozhno poluchat sleduyushij sluchajnyj blok primenyaya algoritm k posledovatelnym naturalnym chislam Schet mozhno nachinat s proizvolnogo naturalnogo chisla Ochevidno chto periodom budet ne bolshe chem 2n dlya n bitnogo blochnogo shifra Takzhe ochevidno chto bezopasnost takoj shemy polnostyu zavisit ot sekretnosti klyucha Kriptograficheski stojkaya hesh funkciya takzhe mozhet byt preobrazovana v KSGPSCh V takom sluchae ishodnoe znachenie schetchika dolzhno ostavatsya v sekrete Odnako nekotorye avtory predosteregayut ot takogo ispolzovaniya hesh funkcij Bolshinstvo potokovyh shifrov rabotaet na osnove generacii psevdosluchajnogo potoka bit kotorye nekotorym obrazom kombiniruetsya pochti vsegda s pomoshyu operacii XOR s bitami otkrytogo teksta Zapusk takogo shifra na posledovatelnosti naturalnyh chisel dast novuyu psevdosluchajnuyu posledovatelnost vozmozhno dazhe s bolee dlinnym periodom Takoj metod bezopasen tolko esli v samom potokovom shifre ispolzuetsya nadyozhnyj KSGPSCh chto ne vsegda tak Opyat zhe nachalnoe sostoyanie schyotchika dolzhno ostavatsya sekretnym Realizacii na osnove matematicheskih zadach Algoritm Blyuma Blyuma Shuba imeet vysokuyu kriptostojkost osnovannuyu na predpolagaemoj slozhnosti faktorizacii celyh chisel Odnako etot algoritm otlichaetsya ochen medlennoj rabotoj Algoritm Blyuma Mikali angl Blum Micali algorithm osnovan na zadache diskretnogo logarifma Specialnye realizacii Sushestvuet celyj ryad prakticheski ispolzuemyh GPSCh kotorye razrabatyvalis s uchetom kriptograficheskoj stojkosti naprimer Algoritm Yarrou angl Yarrow algorithm kotoryj pytaetsya opredelit entropiyu vhodnyh dannyh On ispolzuetsya v FreeBSD OpenBSD i Mac OS X Algoritm Fortuna angl Fortuna algorithm naslednik algoritma Yarrou Specialnyj fajl OS UNIX dev random v chastnosti dev urandom realizovannyj v Linux Funkciya CryptGenRandom predostavlennaya v CryptoAPI kompanii Microsoft ISAAC baziruetsya na variante RC4 PrimechaniyaZvi Gutterman Open to Attack Vulnerabilities of the Linux Random Number Generator angl Data obrasheniya 15 noyabrya 2010 27 fevralya 2011 goda Stealthy Dopant Level Hardware Trojans ot 5 dekabrya 2013 na Wayback Machine o potencialnom vnedrenii troyanov v sostav apparatnogo generatora sluchajnyh chisel Shnajer B 16 Generatory psevdosluchajnyh posledovatelnostej i potokovye shifry Prikladnaya kriptografiya Protokoly algoritmy ishodnye teksty na yazyke Si Applied Cryptography Protocols Algorithms and Source Code in C M Triumf 2002 816 s 3000 ekz ISBN 5 89392 055 4 Shnajer B 2 8 Generaciya sluchajnyh i psevdosluchajnyh posledovatelnostej Prikladnaya kriptografiya Protokoly algoritmy ishodnye teksty na yazyke Si Applied Cryptography Protocols Algorithms and Source Code in C M Triumf 2002 816 s 3000 ekz ISBN 5 89392 055 4 Peter Gutmann Software Generation of Practically Strong Random Numbers angl Proceedings of the 7th USENIX Security Symposium journal 1998 Arhivirovano 4 iyulya 2012 goda Adam Young Moti Yung Malicious Cryptography Exposing Cryptovirology angl sect 3 2 John Wiley 26 Sons 2004 P 416 ISBN 978 0 7645 4975 5 27 maya 2009 goda Yarrow neopr Data obrasheniya 15 noyabrya 2010 8 noyabrya 2012 goda Opisanie funkcii CryptoGenRandom na MSDN angl Microsoft Data obrasheniya 15 noyabrya 2010 Arhivirovano 4 iyulya 2012 goda SsylkiYurij Lifshic Lekciya 9 Psevdosluchajnye generatory Sovremennye zadachi kriptografii Kurs lekcij nedostupnaya ssylka Cryptographic Random Numbers angl angl Zvi Gutterman Benny Pinkas Tzachy Reinman Analysis of the Linux Random Number Generator angl angl NIST SP 800 22
Вершина