Loading AI tools
З Вікіпедії, вільної енциклопедії
Метод «грубої сили» (від англ. 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) |
![]() |
Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її. |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.