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

Криптографічно стійкий генератор псевдовипадкових чисел — генератор псевдовипадкових чисел, який задовільняє додатковим умовам. Зокрема, він має генерувати такі послідовності, які не здатен відрізнити від повністю випадкових послідовностей жоден ефективний алгоритм за поліноміальний час. Іншими словами, жоден статистичний тест не буде здатен відрізнити отриману послідовність псевдовипадкових чисел від насправді випадкової послідовності[1].

Таким чином, генерована послідовність:[2]

  • повинна мати якнайбільш можливий період;
  • не повинна мати прихованих періодів;
  • повинна мати різномірний спектр.

Опис

Безпека деяких алгоритмів шифрування залежить від стійкості генератора випадкових чисел завдяки якому формується ключ або послідовність біт. Шифри з досконалою стійкістю потребують повністю випадкового ключа такої ж довжини, як і вихідний ключ. Проте у більшості випадків, насправді випадкові послідовності біт необхідної довжини не доступні. Тому були розроблені методи отримання псевдовипадкових послідовностей. Такі послідовності можуть справляти враження випадкових, але отримані вони в результаті роботи детермінованого алгоритму. Такі алгоритми називають генераторами псевдовипадкових чисел. Отримавши порівняно невеликий випадковий вхідний рядок (так зване випадкове початкове значення — англ. seed), такі алгоритми здатні обчислити доволі довгі псевдовипадкові послідовності[1].

Звичайні генератори псевдовипадкових послідовностей можуть обчислювати послідовності з якісними статистичними показниками. Отримані послідовності можуть бути придатними для використання в методах Монте-Карло, але непридатними для використання в криптографічних алгоритмах. Наприклад, таємні параметри генераторів псевдовипадкових послідовностей на основі лінійного конгруентного методу або на основі регістра зсуву з лінійним зворотнім зв'язком можуть бути відтворені з доволі невеликої кількості згенерованих ними елементів послідовності. Таким чином, стає можливим відтворити всю згенеровану ними послідовність[1].

Серед відомих методів побудови криптографічно стійких генераторів псевдовипадкових послідовностей важливу роль відіграють генератори на основі односторонніх підстановок[1].

Слід зазначити, що навіть найкращий генератор псевдовипадкових послідовностей потребує джерело дійсно випадкових чисел для отримання початкового значення[1].

Властивості

Оскільки генератори псевдовипадкових чисел є детермінованими алгоритмами, тому буть-хто здатен обчислити елементи генерованої послідовності для заданого початкового значення (англ. seed). А оскільки, зазвичай, алгоритми таких генераторів загально відомі, особливі зусилля мають бути скеровані на те, що б втаємничити їхні початкові значення та унеможливити їхнє обчислення на основі згенерованої послідовності. Крім того, саме початкове значення бажано зробити випадковим та непередбачуваним[3].

Властивості генераторів псевдовипадкових чисел оцінюють з використанням низки кількісних показників, основними з яких є:[4]

  • період (довжина) послідовності псевдовипадкових чисел;
  • основа алфавіту ;
  • ймовірність перекриття в просторі або в часі двох сегментів та , тобто в різних абонентів або в одного абонента протягом часу, так, що ;
  • структурна скритність (еквівалентна складність) послідовності ;
  • кількість (ентропія джерела) ключів для випадку, коли генератор випадкових чисел використовують як джерело ключів;
  • відстань рівнозначності конкретної послідовності ;
  • безпечний час генератора випадкових чисел ;
  • складність формування послідовності ;
  • довжина параметрів зворотного зв'язку;
  • властивості випадковості, рівноймовірності, незалежності та однорідності.

За всіма названими показниками до генератора послідовностей псевдовипадкових чисел висувають низку вимог. Так, період повторення , тобто повинен бути не менше заданого, можливість змінної основи алфавіту , ймовірність перекриття менше допустимої, структурна скритність , ентропія джерела ключів , відстань рівнозначності , безпечний час , тобто не менш допустимих. Крім того, реалізації i повинна задовольняти вимогам випадковості, рівноймовірності, незалежності та однозначності[4].

Крім того, до генераторів псевдовипадкових послідовностей можуть бути висунуті вимоги прямої стійкості (англ. forward unpredictability): попри знання всіх попередніх чисел послідовності наступні числа мають бути непередбачуваними якщо не відоме початкове значення генератора. Зворотна стійкість вимагає унеможливити обчислення початкового значення на основі будь-якої кількості згенерованих чисел послідовності. Кореляція між початковим значенням та згенерованою послідовністю має бути неочевидною, а кожен наступний елемент має справляти враження реалізації випадкової події з імовірністю ½[3].

Стандарти

Загальним підходом до генерування ключів, ключової інформації та параметрів є стандартизація методів, механізмів і практичних (конкретних) алгоритмів їх генерування[4].

Нині розроблені та прийняті регіональні і міжнародні стандарти, у яких визначені вимоги, методи, механізми та алгоритми реалізації генераторів. Оскільки при застосуванні засобів криптографічного захисту інформації необхідністю є відновлення ключів та ключової інформації у просторі й часі, у зазначених стандартах розглянуті лише детерміновані генератори випадкових бітів[4].

Базовими міжнародними стандартами, що стандартизують алгоритми генерації послідовностей випадкових чисел є:[4]

  • міжнародний стандарт ISO/IEC 18031 «Information technology — Random number generation», який визначає алгоритми генерації псевдовипадкових і випадкових чисел, а також визначає статистичні тести перевірки генераторів;
  • міжнародний стандарт ISO/IEC 18032 «Information technology — Prime number generation», який визначає методи генерації простих чисел і методи тестування чисел на простоту;
  • національний стандарт ДСТУ ISO/IEC19790 «Інформаційна технологія — Методи захисту — Вимоги щодо захисту для криптографічних модулів».

Додаткові вимоги до алгоритмів та реалізацій методів і засобів генерації та тестування послідовностей випадкових чисел визначені національними та промисловими стандартами США: FIPS 140-3, ANSI X9.17, ANSI X9.31, ANSI X9.44 та ін., а також рекомендаціями NIST — NIST SP 800-22 і рекомендаціями органу зі стандартизації Німеччини — AIS-20, AIS-31 та інші[4].

Одним із важливих та необхідних напрямків досліджень при створенні ефективних генераторів випадкових чисел та генераторів псевдовипадкових чисел є розробка методів та засобів оцінки статистичних властивостей випадкових послідовностей. Статистичні показники та побудовані на їх основі критеріїв оцінки є інструментом перевірки правильності технічних рішень щодо побудови генераторів випадкових чисел. Дослідження статистичних властивостей здійснюються у рамках методики статистичних випробувань на основі статистичних тестів[4].

Найбільш прийнятними (з точки зору практичного використання) методиками тестування є методики NIST STS, FIPS PUB 140-1, AIS 20 та AIS 31[4].

Приклади

ANSI X9.17

Генератор псевдовипадкових послідовностей визначений у стандарті ANSI X9.17 (Financial Institution Key Management (wholesale)) пройшов сертифікацію та прийнятий як стандарт FIPS. На вході він отримує TDEA (варіант ключів 2) набір ключів k та випадкове початкове число розміром 64 біт s.[5] Для обчислення наступного псевдовипадкового числа послідовності він:

  • Бере поточний час D з найбільшою доступною точністю (мілісекунди, тощо).
  • Обчислює проміжне значення t = TDEAk(D)
  • Обчислює псевдовипадкове число x = TDEAk(st), де ⊕ позначає побітову операцію виключної диз'юнкції.
  • Оновлює значення початкового числа s = TDEAk(xt)

Вади реалізацій

DUHK

Попри відповідність алгоритму формальним вимогам стандартів його реалізації можуть мати вади. Так, в жовтні 2017 року група дослідників оприлюднила доповідь про виявлену ними ваду у деяких апаратних реалізаціях генераторів псевдовипадкових чисел. Зокрема, йдеться про уразливість в реалізації генератора псевдовипадкових чисел ANSI X9.31 Random Number Generator (RNG), коли в пристрої виробником закодовано одне єдине початкове значення генератора замість використання випадкового числа обчисленого іншим генератором випадкових чисел[6].

Генератори ANSI X9.31 мають доволі широке використання в пристроях для генерації ключів шифрування VPN, SSL/TLS, IPsec, тощо[6][7].

Також дослідники розробили алгоритм атаки на знайдену ними вразливість. Алгоритм отримав назву DUHK (англ. Don't Use Hard-coded Keys) та дозволяє зловмиснику відтворити зашифровані дані аж до встановлення сеансового ключа[6].

Дослідникам вдалось встановити 12 продуктів, які успішно пройшли сертифікацію FIPS 140-2, але в яких присутня дана вада[6]. Зокрема, вразливість була виявлена в популярній системі FortiOS v4 версії 4.3.17[7].

Примітки

  1. а б в г д Hans Delfs, Helmut Knebl (2007). 8.1 Computationally Perfect Pseudorandom Bit Generators. Introduction to Cryptography. Information Security and Cryptography (вид. 2-ге). Springer. ISBN 978-3-540-49243-6.
  2. Олег Ігорович Гарасимчук, Володимир Миколайович Максимович. Генератори псевдовипадкових чисел, їх застосування, класифікація, основні методи побудови і оцінка якості // Захист інформації. — 2003. — Т. 5, вип. 16. — DOI:10.18372/2410-7840.5.4270. Архівовано з джерела 2 червня 2018. Процитовано 6 листопада 2017.
  3. а б 1.1.2 Unpredictability. A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications (PDF) (Звіт). Special Publication (вид. Revision 1a). NIST. квітень 2010. NIST 800-22. Архів оригіналу (PDF) за 18 листопада 2017. Процитовано 7 листопада 2017.
  4. а б в г д е ж и О. А. Замула, Д. О. Семченко, Ю. В. Землянко. Аналіз і обґрунтування критеріїв і показників ефективності криптографічних генераторів псевдовипадкових чисел // Системи обробки інформації. — 2014. — Вип. 120. — С. 131-136. Архівовано з джерела 8 листопада 2017. Процитовано 8 листопада 2017.
  5. Handbook of Applied Cryptography [Архівовано 16 лютого 2012 у Wayback Machine.], Alfred Menezes, Paul van Oorschot, and Scott Vanstone, CRC Press, 1996, Chapter 5 Pseudorandom Bits and Sequences [Архівовано 8 лютого 2012 у Wayback Machine.] (PDF)
  6. а б в г Catalin Cimpanu (24 жовтня 2017). DUHK Crypto Attack Recovers Encryption Keys, Exposes VPN Connections, More. Bleeping Computer. Архів оригіналу за 25 жовтня 2017. Процитовано 7 листопада 2017.
  7. а б Shaanan Cohney, Nadia Heninger, and Matthew D. Green. Practical state recovery attacks against legacy RNG implementations. Архівовано з джерела 5 листопада 2017. Процитовано 7 листопада 2017.

Література

Див. також

Посилання


Read other articles:

Provinsi (kata tidak baku: propinsi)[1] adalah suatu satuan teritorial, seringnya dijadikan nama sebuah wilayah administratif pemerintahan di bawah wilayah negara atau negara bagian. Kata ini merupakan kata serapan dari bahasa Belanda provincie yang berasal dari bahasa Latin dan pertama kalinya digunakan di Kekaisaran Romawi Kuno, yang merupakan unit teritorial dan administratif utama dari kepemilikan teritorial Kekaisaran Romawi di luar Italia. Mereka membagi wilayah kekuasaan mereka...

 

 

Basilika Santa Anna dari KongoGereja Basilika Minor Santa Anna dari Kongo di BrazzavillePrancis: Basilique Sainte-Anne-du-Congocode: fr is deprecated Basilika Santa Anna dari KongoLokasiBrazzavilleNegara Republik KongoDenominasiGereja Katolik RomaArsitekturStatusBasilika minorStatus fungsionalAktifAdministrasiKeuskupan AgungKeuskupan Agung Brazzaville Basilika Santa Anna dari Kongo, Brazzaville (Prancis: Basilique Sainte-Anne-du-Congocode: fr is deprecated ) adalah sebuah gereja basilika...

 

 

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Maret 2016. SMA Negeri 1 BondowosoInformasiJurusan atau peminatanIPA dan IPSRentang kelasX, XI IPA, XI IPS, XII IPA, XII IPSKurikulumKurikulum Tingkat Satuan PendidikanAlamatLokasiJl. Curahdami, Bondowoso, Jawa TimurMoto SMA Negeri (SMAN) 1 Bondowoso, merupakan sala...

2 pence 1797. Britania Raya, George III. Tembaga. Penny (jamak pence) adalah sebuah koin (jamak pennies) atau satuan mata uang (jamak pence) yang digunakan di beberapa negara berbahasa Inggris. Penny biasanya merupakan denominasi terkecil dalam sistem mata uang. Nilai ⅟100 pound sterling Britania, pound Irlandia yang sudah tidak digunakan, pound Gibraltar, pound Santa Helena, pound Kepulauan Falkland. ⅟240 pound sterling Britania atau Irlandia sebelum desimalisasi pada 15 Februari 1971, p...

 

 

Children's fantasy novel by Paul Stewart and Chris Riddell This article's plot summary may be too long or excessively detailed. Please help improve it by removing unnecessary details and making it more concise. (May 2015) (Learn how and when to remove this template message) For the 1992 novel by Nicholson Baker, see Vox (Nicholson Baker novel). Vox First editionAuthorPaul Stewart, Chris RiddellCover artistChris RiddellCountryUnited KingdomLanguageEnglishSeriesThe Edge ChroniclesGenreChil...

 

 

RS Islam PKU Muhammadiyah DepokMuhammadiyahGeografiLokasiJalan Raya Bedahan №18, Bedahan, Kec. Sawangan, Kota Depok, Jawa Barat 16519OrganisasiJenisDAfiliasi dengan universitas Muhammadiyah Berkas:PMI.svg Palang Merah Indonesia Dinas Kesehatan Kota Depok RS Muhammadiyah Depok atau memiliki nama lengkap RS Islam PKU Muhammadiyah Depok adalah sebuah calon rumah sakit swasta yang berada di Kota Depok, Jawa Barat. Rumah sakit ini direncanakan akan dibangun atas prakarsa organisasi Islam Muhamma...

Huruf KirilGe dengan diakritik penurun Penggunaan Fonetis:[ɣ], [ʁ], [ɢ]Alfabet KirilHuruf SlaviaАА́А̀А̂А̄ӒБВГҐДЂЃЕЕ́ÈЕ̂ЁЄЖЗЗ́ЅИИ́ЍИ̂ЙІЇЈКЛЉМНЊОŌПРСС́ТЋЌУУ́ У̀У̂ӮЎФХЦЧЏШЩЪЫЬЭЮЯHuruf non-SlaviaӐА̊А̃Ӓ̄ӔӘӘ́Ә̃ӚВ̌ҒГ̑Г̣Г̌ҔӺҒ̌ӶД̌Д̣Д̆ӖЕ̄Е̃Ё̄Є̈ӁҖӜҘӞЗ̌З̱З̣ԐԐ̈ӠӢИ̃ҊӤҚӃҠҞҜК̣ԚӅԮԒӍӉҢԨӇҤО́О̀О̆О̂О̃ӦӦ̄ӨӨ̄Ө́Ө̆ӪҨԤР̌ҎҪС̣С̱Т...

 

 

Halaman ini berisi artikel tentang seri televisi 2010. Untuk waralaba berjudul sama, lihat Pretty Little Liars (waralaba). Untuk kegunaan lain, lihat Pretty Little Liars (disambiguasi). Pretty Little LiarsGenre Drama remaja Misteri Cerita seru Fiksi kejahatan BerdasarkanPretty Little Liars oleh Sara ShepardPengembangI. Marlene KingPemeranTroian BellisarioAshley BensonHolly Marie CombsLucy HaleIan HardingBianca LawsonLaura LeightonChad LoweShay MitchellNia PeeplesSasha PieterseJanel ParrishTyl...

 

 

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016) أرمينيا في الألعاب الأولمبية علم أرمينيا رمز ل.أ.د.  ARM ل.أ.و. اللجنة الأولمبية الأرمينيةرابط إض...

Philippine record label branch of Universal Music Group This article is about the Philippine branch of the Universal Music Group. For the unrelated Philippine label, see Universal Records (Philippines). UMG Philippines Inc.Company typeSubsidiaryTraded asUniversal Music Philippines (outside Philippine territory)IndustryMusicPredecessor PolyCosmic Records (1993–1997) PolyGram Records (1997–1999) MCA Universal (1999–2004) MCA Music Inc. (2004–2021) Founded1993Headquarters12th Floor, The ...

 

 

County in Michigan, United States For the county of Oakland, California, see Alameda County. County in Michigan, United StatesOakland County, MichiganCountyCounty of OaklandTop-to-bottom, left-to-right: Troy's skyline, Southfield's skyline, Rackham Fountain (at the Detroit Zoo), National Shrine of the Little Flower Basilica (Royal Oak), Downtown Pontiac, Downtown Royal Oak (downtown Detroit on the horizon) FlagSealLogoLocation within the state of MichiganCities and Townships in the countyCoun...

 

 

Method of preserving human remains Embalmer redirects here. For other uses, see The Embalmer, Embalmer (band), and Embalming (manga). Embalming is the art and science of preserving human remains by treating them (in its modern form with chemicals) to forestall decomposition. This is usually done to make the deceased suitable for viewing as part of the funeral ceremony or keep them preserved for medical purposes in an anatomical laboratory. The three goals of embalming are sanitization, presen...

Pertempuran GibraltarBagian dari Perang Delapan Puluh Tahun Pertempuran Gibraltar oleh Hendrick Cornelisz Vroom.Tanggal25 April 1607LokasiTeluk Gibraltar, dekat GibraltarHasil Kemenangan BelandaPihak terlibat Republik Belanda SpanyolTokoh dan pemimpin Jacob van Heemskerk † Juan Álvarez de Avilés †Kekuatan 26 kapal perang4 kapal pedagang 21 kapal perangKorban 100 tewas60 terluka 4.000 tewas21 kapal hancur Pertempuran Gibraltar terjadi pada tanggal 25 April 1607 selama Perang Delapan Pulu...

 

 

Overview of the politics of The Bahamas This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Politics of the Bahamas – news · newspapers · books · scholar · JSTOR (March 2019) (Learn how and when to remove this message) Politics of The Bahamas Executive Monarch Charles III Governor-General (list) Cynthia A. Pratt...

 

 

Voce principale: Delfino Pescara 1936. Pescara CalcioStagione 2005-2006Sport calcio Squadra Pescara Allenatore Maurizio Sarri All. in seconda Vincenzo Vivarini Presidente Dante Paterna Serie B11º posto Coppa ItaliaPrimo turno Maggiori presenzeCampionato: Pesaresi e Vigna (36)Totale: Pesaresi e Vigna (36) Miglior marcatoreCampionato: Matteini (9)Totale: Matteini (9) StadioAdriatico Abbonati1 414 Maggior numero di spettatori5 366 vs Brescia(15 ottobre 2005) Minor numero di spet...

Cet article est une ébauche concernant un aéroport chinois. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Pour les articles homonymes, voir CGO. Aéroport international de Zhengzhou Xinzheng郑州新郑国际机场Zhèngzhōu Xīnzhèng Guójì Jīchǎng Localisation Pays Chine Province Henan Ville Zhengzhou Coordonnées 34° 31′ 11″ nord, 113° 50′ 27″ est Altitude 151 ...

 

 

Irish Football League redirects here. For the football league of the Republic of Ireland, see League of Ireland. This article treats the Northern Ireland Football League and all previous Northern Irish national football league systems since 1890 collectively as a single article. Football leagueNorthern Ireland Football LeagueFounded1890; 134 years ago (1890) (as Irish Football League)CountryNorthern Ireland (since 1921)Ireland (1890–1921)ConfederationUEFADivisionsNIFL Prem...

 

 

French actress (1921–1985) Simone SignoretSignoret in 1947BornSimone Henriette Charlotte Kaminker(1921-03-25)25 March 1921Wiesbaden, GermanyDied30 September 1985(1985-09-30) (aged 64)Autheuil-Authouillet, FranceOccupationActressYears active1942–1985Spouses Yves Allégret ​ ​(m. 1944; div. 1949)​ Yves Montand ​ ​(m. 1951)​ ChildrenCatherine Allégret Simone Signoret (French: [simɔn siɲɔʁɛ&...

Albinea Albinea (Italien) Staat Italien Region Emilia-Romagna Provinz Reggio Emilia (RE) Lokale Bezeichnung Albinèa Koordinaten 44° 37′ N, 10° 36′ O44.61666666666710.6166Koordinaten: 44° 37′ 0″ N, 10° 36′ 0″ O Höhe 166 m s.l.m. Fläche 44 km² Einwohner 8.788 (31. Dez. 2022)[1] Postleitzahl 42020 Vorwahl 0522 ISTAT-Nummer 035001 Bezeichnung der Bewohner Albinetani Schutzpatron San Gaetano Website ...

 

 

Ne doit pas être confondu avec Cherish, Sherry, Cheiry, Chérie, Chéri, Cherie ou Cherry. Chery Automobile Création 8 janvier 1997 Forme juridique Entreprise d'État Slogan Fun to drive Siège social Wuhu, Anhui Chine Direction Yin Tongyue (Président-Directeur Général) [1] Actionnaires République populaire de Chine (100 %) Activité Automobile Produits Automobile Filiales Qoros (25%) et Chery Jaguar Land Rover (50%) Partenaires CAOA Site web http://www.cheryinternational.com...