Метод «грубої сили» (від англ. brute force; або повний перебір) — метод рішення криптографічної задачі шляхом перебору всіх можливих варіантів ключа. Складність повного перебору залежить від кількості всіх можливих рішень задачі. Якщо простір рішень дуже великий, то повний перебір може не дати результатів протягом декількох років або навіть століть.
Будь-яка задача з класу NP може бути вирішена повним перебором. При цьому, навіть якщо обчислення цільової функції від кожного конкретного можливого рішення задачі може бути здійснена за поліноміальний час, в залежності від кількості всіх можливих рішень повний перебір може зажадати експоненціального часу роботи.
У криптографії на обчислювальній складності повного перебору ґрунтується оцінка криптостійкості шифрів. Зокрема, шифр вважається криптостійким, якщо не існує методу «злому» істотно більш швидкого ніж повний перебір всіх ключів. Криптографічні атаки, засновані на методі повного перебору, є найуніверсальнішими, але водночас і найповільнішими.
На методі грубої сили базується ата́ка по́вного перебо́ру — вид криптоаналізу, який полягає у переборі ключів, з множини можливих.
Ефективний для нескладних алгоритмів шифрування та алгоритмів, які використовують ключі довжиною до 64-біт.
Для сучасних алгоритмів, які використовують ключі довжиною від 128-біт, є неефективним.
Методи оптимізації повного перебору
Метод гілок і меж
Для прискорення перебору метод гілок і меж використовує відсів підмножин допустимих рішень, про які наперед відомо що вони не містять оптимальних рішень.
Розпаралелювання обчислень
Для збільшення швидкості підбору ключа використовується розпаралелювання обчислень. Існує два підходи до розпаралелювання:
- побудова конвеєра. Нехай алгоритм співвідношення можна уявити у вигляді ланцюжка найпростіших дій (операцій). Візьмемо процесорів, задамо їх порядок, -ий процесор виконує три однакові за часом операції:
- отримання даних від — -го процесора;
- виконання операції;
- передача даних -му процесору.
Тоді конвеєр з послідовно з'єднаних, паралельно і синхронно працюючих процесорів працює зі швидкістю , де — швидкість виконання однієї операції одним процесором.
- Другий підхід полягає що множина всіх можливих ключів розбивається на непересічні підмножини. Система з машин перебирає ключі так, що -та машина здійснює перебір ключів з множини . Система припиняє роботу, якщо одна з машин знайшла ключ. Найважче — це розділення вихідної множини. Але якщо кожен процесор почне обчислення з якогось довільного ключа, то час перебору збільшиться, але схема значно спроститься. Середнє число кроків у цьому випадку становить , де — число елементів у множині ключів, а — число процесорів.
Приклад тривалості підбору паролів
У переліку представлено оцінний час повного перебору паролів в залежності від їх довжини. Передбачається, що в паролі можуть використовуватися 36 різних символів (латинські літери одного регістру та цифри), а швидкість перебору становить 100 000 паролів в секунду (порядок представлених даних в рядку: Кількість знаків — Кількість варіантів — Час перебору):
Кількість знаків | Кількість варіантів | Час перебору |
---|---|---|
1 | 36 | менше секунди |
2 | 1296 | менше секунди |
3 | 46 656 | менше секунди |
4 | 1 679 616 | 17 секунд |
5 | 60 466 176 | 10 хвилин |
6 | 2 176 782 336 | 6 годин |
7 | 78 364 164 096 | 9 днів |
8 | 2,821 109 9×1012 | 11 місяців |
9 | 1,015 599 5×1014 | 32 роки |
10 | 3,656 158 4×1015 | 1162 роки |
11 | 1,316 217 0×1017 | 41 823 роки |
12 | 4,738 381 3×1018 | 1 505 615 років |
Таким чином, паролі довжиною до 6 символів у загальному випадку не є надійними.
Див. також
Цю статтю треба для відповідності Вікіпедії. (березень 2017) |
Ця стаття не містить . (січень 2014) |
Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Metod gruboyi sili vid angl brute force abo povnij perebir metod rishennya kriptografichnoyi zadachi shlyahom pereboru vsih mozhlivih variantiv klyucha Skladnist povnogo pereboru zalezhit vid kilkosti vsih mozhlivih rishen zadachi Yaksho prostir rishen duzhe velikij to povnij perebir mozhe ne dati rezultativ protyagom dekilkoh rokiv abo navit stolit Bud yaka zadacha z klasu NP mozhe buti virishena povnim pereborom Pri comu navit yaksho obchislennya cilovoyi funkciyi vid kozhnogo konkretnogo mozhlivogo rishennya zadachi mozhe buti zdijsnena za polinomialnij chas v zalezhnosti vid kilkosti vsih mozhlivih rishen povnij perebir mozhe zazhadati eksponencialnogo chasu roboti U kriptografiyi na obchislyuvalnij skladnosti povnogo pereboru gruntuyetsya ocinka kriptostijkosti shifriv Zokrema shifr vvazhayetsya kriptostijkim yaksho ne isnuye metodu zlomu istotno bilsh shvidkogo nizh povnij perebir vsih klyuchiv Kriptografichni ataki zasnovani na metodi povnogo pereboru ye najuniversalnishimi ale vodnochas i najpovilnishimi Na metodi gruboyi sili bazuyetsya ata ka po vnogo perebo ru vid kriptoanalizu yakij polyagaye u perebori klyuchiv z mnozhini mozhlivih Efektivnij dlya neskladnih algoritmiv shifruvannya ta algoritmiv yaki vikoristovuyut klyuchi dovzhinoyu do 64 bit Dlya suchasnih algoritmiv yaki vikoristovuyut klyuchi dovzhinoyu vid 128 bit ye neefektivnim Metodi optimizaciyi povnogo pereboruMetod gilok i mezh Dlya priskorennya pereboru metod gilok i mezh vikoristovuye vidsiv pidmnozhin dopustimih rishen pro yaki napered vidomo sho voni ne mistyat optimalnih rishen Rozparalelyuvannya obchislen Dlya zbilshennya shvidkosti pidboru klyucha vikoristovuyetsya rozparalelyuvannya obchislen Isnuye dva pidhodi do rozparalelyuvannya pobudova konveyera Nehaj algoritm spivvidnoshennya mozhna uyaviti u viglyadi lancyuzhka najprostishih dij operacij Vizmemo N displaystyle N procesoriv zadamo yih poryadok i displaystyle i ij procesor vikonuye tri odnakovi za chasom operaciyi otrimannya danih vid i 1 displaystyle i 1 go procesora vikonannya operaciyi peredacha danih i 1 displaystyle i 1 mu procesoru Todi konveyer z N displaystyle N poslidovno z yednanih paralelno i sinhronno pracyuyuchih procesoriv pracyuye zi shvidkistyu v 3 displaystyle v 3 de v displaystyle v shvidkist vikonannya odniyeyi operaciyi odnim procesorom Drugij pidhid polyagaye sho mnozhina K displaystyle K vsih mozhlivih klyuchiv rozbivayetsya na neperesichni pidmnozhini Sistema z Q displaystyle Q mashin perebiraye klyuchi tak sho i displaystyle i ta mashina zdijsnyuye perebir klyuchiv z mnozhini K i i 1 Q displaystyle K i i 1 Q Sistema pripinyaye robotu yaksho odna z mashin znajshla klyuch Najvazhche ce rozdilennya vihidnoyi mnozhini Ale yaksho kozhen procesor pochne obchislennya z yakogos dovilnogo klyucha to chas pereboru zbilshitsya ale shema znachno sprostitsya Serednye chislo krokiv u comu vipadku stanovit K N displaystyle K N de K displaystyle K chislo elementiv u mnozhini klyuchiv a N displaystyle N chislo procesoriv Priklad trivalosti pidboru parolivU pereliku predstavleno ocinnij chas povnogo pereboru paroliv v zalezhnosti vid yih dovzhini Peredbachayetsya sho v paroli mozhut vikoristovuvatisya 36 riznih simvoliv latinski literi odnogo registru ta cifri a shvidkist pereboru stanovit 100 000 paroliv v sekundu poryadok predstavlenih danih v ryadku Kilkist znakiv Kilkist variantiv Chas pereboru Kilkist znakiv Kilkist variantiv Chas pereboru 1 36 menshe sekundi 2 1296 menshe sekundi 3 46 656 menshe sekundi 4 1 679 616 17 sekund 5 60 466 176 10 hvilin 6 2 176 782 336 6 godin 7 78 364 164 096 9 dniv 8 2 821 109 9 1012 11 misyaciv 9 1 015 599 5 1014 32 roki 10 3 656 158 4 1015 1162 roki 11 1 316 217 0 1017 41 823 roki 12 4 738 381 3 1018 1 505 615 rokiv Takim chinom paroli dovzhinoyu do 6 simvoliv u zagalnomu vipadku ne ye nadijnimi Div takozhMetod gilok i mezh Cyu stattyu treba vikifikuvati dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit dodavannyam dorechnih vnutrishnih posilan abo vdoskonalennyam rozmitki statti berezen 2017 Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno sichen 2014 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi