Крипто-форум crprogram.16mb.com

Програмування, Delphi, криптографія, криптоаналіз, шифри, вихідні коди, вирішення задач, приклади програм

Часовий пояс: UTC десь + 2 години




Розпочати нову тему Відповісти  [ 18 повідомлень ] 
Автор Повідомлення
 Заголовок повідомлення: RSA: будь який алгоритм шифрування є потенційно небезпечним
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
Наведемо метод, який демонструє те, що будь який алгоритм шифрування є потенційно небезпечним, але показати його повну безпечність можливо лише приклавши зусилля, яки більші за його розшифрування методом грубої сили.
Метод базується на публікації у №5/2013 журналу “Eastern European Scientific Journal” стаття "NP not equal to P".
У наведеній статті доведено, що відповідь 1 або 0 може бути представлена у вигляді ДНФ від початкових даних, причому заперечення беруться лише від початкових даних, причому ДНФ відповіді при цьому формується лише за допомогою «ТА» або «АБО».
Розглянемо наступний малюнок:
Приєднання файлів:
разбор шифротексту.JPG [27.67 KiB]
Скачали: 0

Червоне та Зелене вибираються таким чином, щоб омано було представити Червоне «ТА» Зелене. Тоді зрозуміло, що кожне з від 1 до n^h можливо отримати меншими зусиллями, просто за допомогою «ТА».
Що сильно зменшує складність.
Потім кожне з зелених або червоних можливо спрощувати цим самим методом.
Що і потрібно довести.
Примітка 1: «якась перестановка» для кожного з від 1 до n^h може бути різна.
Примітка 2: може не входити в від 1 до n^h о-маленьке від кількості аналізованих кон’юнктів. (це буде означати типовий випадок).
Примітка 3: можливо провести аналіз невеликого за обсягом величини шифротексту та ключів, для евристичних міркувань щодо стійкості великих за обсягом ключів.
Copyleft Koval V., Bilan I..


Повернутися наверх
  
 
 Заголовок повідомлення: Re: будь який алгоритм шифрування є потенційно небезпечним
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 282
mathbilan писал(а):
Наведемо метод, який демонструє те, що будь який алгоритм шифрування є потенційно небезпечним, але показати його повну безпечність можливо лише приклавши зусилля, які більші за його розшифрування методом грубої сили.

Твердження не вірне в принципі.
Такі шифри існують, і для доведення їх абсолютної стійкості не потрібні зусилля більші ніж атака повного перебору.

Тому викликає сумнів вірність вашого доведення:
(99,999999% що воно теж не вірне).
mathbilan писал(а):
Червоне та Зелене вибираються таким чином, щоб омано було представити Червоне «ТА» Зелене. Тоді зрозуміло, що кожне з від 1 до n^h можливо отримати меншими зусиллями, просто за допомогою «ТА».
Що сильно зменшує складність.
Потім кожне з зелених або червоних можливо спрощувати цим самим методом.
Що і потрібно довести.

Якщо чесно - нічого не зрозуміло в доведенні.

Напишіть детально - який саме шифр мається на увазі?
Що означають злені/червоні зони у перестановці?


Повернутися наверх
  
 
 Заголовок повідомлення: Re: будь який алгоритм шифрування є потенційно небезпечним
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
поперше, подяка за запитання, відповім залюбки і на подальші запитання.
Мова іде про шифри з відкритим ключем.
Червоні та Зелені означають розбиття деякої підмножени коньюнктів С (таких підмножин коньюнктів n^h)
на дві частини -- червону та зелену, причому підмножина коньюнктів С є добутком (логічним) червоних "на" зелені.
Чи іншими словами А "ТА" В=С
тоді якщо ми отримаємо А це Зелене, а В це Червоне, то перебирати ми можемо не С, а лише А, В.
а А, В ми можемо розкладати тим самим методом, як колись розкладали С.
Таким чином ми можемо прийти до множинам коньюнктів, які вже перебираються, наприклад 10 змінних у коньюнкті (2^10 - вже перебирається).
оптім ідемо по оберненому шляху, та отримуємо 1 або 0 на к-й позиції тексту, який нас так цікавить, тобто у тексті, який зашифрували.
якщо щось знов не зрозуміло, поясню, більш детально.
з повагою Білан І.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: будь який алгоритм шифрування є потенційно небезпечним
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 5
На малюнку йдеться про перестановки - де ви знайшли перестановки у шифрах з відкритим ключем?

mathbilan писал(а):
на дві частини -- червону та зелену, причому підмножина коньюнктів С є добутком (логічним) червоних "на" зелені.
Чи іншими словами А "ТА" В=С

Ви використовуєте логічне множення у таких шифрах? :shock:
Там же ніколи не було логічних операцій "та",

Приклад, формула для RSA
Код:
C = (M ^ e ) mod n
P = (C ^ d ) mod n

M - повідомлення,
e,n - відкритий(публічний) ключ,
d,n - заритий ключ.

(e як правило
3 = 11,
17 = 10001,
257 = 100000001,
65537 = 10000000000000001.)

Де тут перестановки/логічні множники?

p.s.:
Або ви дійсно "заблукали" і вірите у істинність ваших доведень, або ж свідомо зайняті псевдонауковою діяльністю.
Що і не дивно, зважаючи у якому стані зараз українська наука.

Цій темі місце тут.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: будь який алгоритм шифрування є потенційно небезпечним
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 5
Єдиний вихід:
наведіть тут детальний приклад для RSA починаючи з відкритого тексту(наприклад, "AAABBB" і закінчуючи шифротекстом для невеликого числа,
наприклад, p та q у межах 10000...20000 (простих чисел там достатньо).

Якщо ви перевіряли інший алгоритм - розкажіть про нього.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: будь який алгоритм шифрування є потенційно небезпечним
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
тоді давайте, з початку:
1. беремо усі можливі відкриті ключі, та зашифровані їми тексти, де у к-й позиції незашифрованого тексту стоїть 1.
отримуємо ДНФ, рівність якої 1 ми отримуємо при підстановці зашифрованого тексту, та відкритого ключа.
2.якщо ми можемо розкласти цю ДНФ на множини коньюнктів тієї самої ДНФ на n^h множин коньюнктів С_і (1<=і<=n^h) таким чином, щоб кожна з С_і ми мали змогу отримати не повним перебором усіх коньюнктів, а перебором лише підмножин змінних ціх коньюнктів, а саме зелених змінних та червоних змінних (А_і та В_і)
та С_і=А_і*В_і
то зрозуміло, що складність отримання С_і стане складністю отримання А_і та В_і.
3. до А_і, В_і ми маємо змогу застосувати той саме метод, що і до С_і у пункті 2, і так далі, до отримання коньюнктів невеликого розміру.
тепер зрозуміло?
вибачтесь за стан науки в Україні :)
з повагою Білан І.


Востаннє редагувалось mathbilan в 23 гру 2013, 12:26, всього редагувалось 1 раз.

Повернутися наверх
  
 
 Заголовок повідомлення: Re: будь який алгоритм шифрування є потенційно небезпечним
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
Шановний Moctky!
навіть для RSA з відкритим ключем у межах 10 біт мій компьютер не в змозі перебрати набір навіть двох множин коньюнктів, а не то щоб n^h :)
це випливає з того, що там буде як мініум 2^20/2 конюнктів а навіть 2-х підмножин там буде занадто багато :)
а ще по дві підмножини для кожного в С_і
це справа для суперкомпьютерів :)


Повернутися наверх
  
 
 Заголовок повідомлення: Re: будь який алгоритм шифрування є потенційно небезпечним
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 5
Добре, покажіть детальний приклад для
RSA
p = 23
q = 37
відкритий текст та інші потрібні параметри виберіть самі.

Покажіть множину шифротестів, множину відкритих текстів, розкладення на "множини коньюнктів".

Інакше це виглядає як твердження
Цитата:
я можу множити числа більші мільйона "в умі", а додати 2+3 не можу.


Тільки не говоріть,що ваш домашній ПК не зможе це зробити.
RSA для таких чисел зламає навіть школяр.


Востаннє редагувалось Moctky в 23 гру 2013, 12:44, всього редагувалось 1 раз.

Повернутися наверх
  
 
 Заголовок повідомлення: Re: будь який алгоритм шифрування є потенційно небезпечним
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
добре, на завтра буде готово!
з повагою Білан І.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: будь який алгоритм шифрування є потенційно небезпечним
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
Moctky писал(а):

Тільки не говоріть,що ваш домашній ПК не зможе це зробити.
RSA для таких чисел зламає навіть школяр.

тільки цього не обіцяю


Повернутися наверх
  
 
 Заголовок повідомлення: Re: RSA: будь який алгоритм шифрування є потенційно небезпеч
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
Відповідь:
Таким чином 1-й множник 37, другий 23, тобто відкритий ключ складається з (2^4<23<2^5, та 2^5<37<2^6) з 4+5=9 бітів.
Переберемо усі відкриті ключі з 9 бітів, та занесемо їх у масив T (нехай е-фіксоване).
Потім для кожного відкритого ключа з Т переберемо усі тексти, що потрібно зашифрувати, (тобто у RSA для нашого випадку з 9 біт, причому на к-й позиції 1-ця )
Приклад 1:
Нехай к=2
000000010 шифруємо 1-м відкритім ключем та заносимо у масив У разом з 1-шим відкритим ключем на 1-ший рядок масиву У.
100000010 шифруємо 1-м відкритім ключем та заносимо у масив У разом з 1-шим відкритим ключем на 2-гий рядок масиву У.
110000010 шифруємо 1-м відкритім ключем та заносимо у масив У разом з 1-шим відкритим ключем на 3-тій рядок масиву У.
101000010 шифруємо 1-м відкритім ключем та заносимо у масив У разом з 1-шим відкритим ключем на 4-тий рядок масиву У.
………………………
Все, тексти закінчились!
Знов, для другого відкритого ключа:
000000010 шифруємо 2-м відкритім ключем та заносимо у масив У разом з 2-гим відкритим ключем на 2^8+1-ший рядок масиву У.
100000010 шифруємо 2-м відкритім ключем та заносимо у масив У разом з 2-гим відкритим ключем на 2^8+2-гий рядок масиву У.
110000010 шифруємо 2-м відкритім ключем та заносимо у масив У разом з 2-гим відкритим ключем на 2^8+3-тій рядок масиву У.
101000010 шифруємо 2-м відкритім ключем та заносимо у масив У разом з 2-гим відкритим ключем на 2^8+4-тий рядок масиву У.
………………………
Все, тексти закінчились!
Знов, для третього відкритого ключа:
Те саме
……………………………
Все, відкриті ключі закінчились!
У масиві У записані у кожному рядку, у двійковому коді:відкритий ключ, зашифрований ним текст (примітка, текст у незашифрованому вигляді на к-й позиції=1)
Таким чином по масиву У ми можемо перейти до ДНФ, яка =1<=> коли на к-й позиції у незашифрованому тексті стоїть 1.
Наступним чином: кожен коньюнкт – рядок масиву У, де 0- заперечення змінної
1-ця – твердження змінної.
Тоді, якщо ми підставимо значення відкритого ключа, та зашифрованого тексту, в якого 0-лі на місті заперечень, а 1-ці на місті тверджень, ми отримаємо коньюнкт, який = 1, тобто уся ДНФ =1,
Тобто на к-й позиції незашифрованого тексту стоїть 1.
Інакше, якщо усі коньюнкти нашої ДНФ =0, то і ДНФ=0, а так як ми перебрали УСІ зашифровані тексти з усіма відкритими ключами, де у незашифрованому тексті на к-му місті стоїть 1, то на к-му місті у незашифрованому тексті в такому випадку стоїть 0.
Тепер зрозуміло, чому ПК це не потягне?
Далі, як можна економніше обчислити цю кляту ДНФ побудовану по масиву У?
В нас дві можливості: або за допомогою «ТА», або за допомогою «АБО».
«АБО» не дає зменшення числа коньюнктів.
«ТА» дає змогу перемножити кількість коньюнктів , тобто застосовуючи «ТА» поліноміальне число разів, ми отримаємо експоненційну кількість коньюнктів (що нам і потрібно).
Якщо буде підмножина (назвемо її F) коньюнктів ДНФ, причому, змінні з цих коньюнктів можливо розбити на дві частини так, що якщо першу частину змінних помножимо за допомогою «ТА» на другу частину змінних, то отримаємо F.
Тобто наприклад так:
Приклад 2:
Тут 1—твердження, 0—заперечення, н—пропуск.
(10нн+11нн) «ТА»(нн01+нн10)=1001+1101+1010+1110
Зрозуміло, що якщо вдасться, тобто шифрування не стійке до взлому, то обчислення таким чином можливо дуже спростити.
При цьому саме тут виникають перестановки, бо «н» у прикладі 2, наприклад можуть бути розташовані таким чином:
(1н0н+1н1н) «ТА»(н0н1+н1н0)=1001+1011+1100+1110
Таким чином, при невдалому шифрі можливо, за поліноміальне число кроків по БУДЬЯКОМУ зашифрованому тексту та БУДЬЯКОМУ відкритому ключу можливо отримати відповідь 0 чи 1 стоїть на к-му місті у незашифрованому тексті.
Прикладна значимість алгоритму:
На невеликих ключах, можливо знаходження абсолютно нових за ідеєю методів криптоаналізу.
Для RSA це може значити взлом не факторизуючи відкритий ключ.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: RSA: будь який алгоритм шифрування є потенційно небезпеч
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 282
Цікавий поворот дискусії.

Отже:

Відкритий ключ 9 біт, n = 2^9 = 512

Кількість відкритих текстів для перебору 256

Заповнюємо масив 2^9*(2^(9-1)) = 512*256 = (2^17) = 131 072

Ми на етапі, коли всі ключі закінчились.

Йдемо далі
Цитата:
ми перебрали УСІ зашифровані тексти з усіма відкритими ключами, де у незашифрованому тексті на к-му місті стоїть 1

Припустімо, перебрали.
Для цього нам не потрібні ніякі коньюкти та функції, достатньо простої таблиці.

Цитата:
Тепер зрозуміло, чому ПК це не потягне?

Чому ж не потягне - якраз даний приклад (131072 пари ВТ-ШТ) потягне.
Тільки це називається атака повного перебору - і наукової новизни у ній немає.

Цитата:
Далі, як можна економніше обчислити цю кляту ДНФ побудовану по масиву У?

йдемо далі
Цитата:
Наступним чином: кожен коньюнкт – рядок масиву У
«ТА» дає змогу перемножити кількість коньюнктів , тобто застосовуючи «ТА» поліноміальне число разів, ми отримаємо експоненційну кількість коньюнктів (що нам і потрібно).

отже нам потрібно
логічно перемножувати елементи таблиці, їх всього 131072

Нагадаю правила логічного множення
(операція "ТА")
0*0=0
0*1=0
1*0=0
1*1=1


їх доведеться множити
всього (1310072*1310071)/2
858 143 667 556 раз

Що ж це виходить?
Для того щоб зламати шифр перебравши всього ( у найгіршому випадку) 2500 варіантів, нам знадобиться мало не
10^11 множень?

Цитата:
Таким чином, при невдалому шифрі можливо, за поліноміальне число кроків по БУДЬЯКОМУ зашифрованому тексту та БУДЬЯКОМУ відкритому ключу можливо отримати відповідь 0 чи 1 стоїть на к-му місті у незашифрованому тексті.

відкрию вам страшну таємницю,
тільки нікому, чуєте НІКОМУ :) ,
для RSA
достатньо виконати ~4-ри операції шифрування щоб отримати 1 на к-му місці ВТ.

То ми відкрили новий метод криптоаналізу? :D

Висновок:
переношу вашу тему в розділ "Хлам, off topic, думки, інше"
(ми дорожимо репутацією свого форуму,
нехай у нас тут і немає професорів/академіків,
але є команда професіоналів,
соромно перед ними коли подібні теми висять у головних розділах форуму.).

До речі, ви говорите що викладаєте у ВУЗ
я так і не помітив ваших студентів тут.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: RSA: будь який алгоритм шифрування є потенційно небезпеч
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 282
Для того ж AES-128 можливо теж побудувати таблицю ((2^128)^2) а тоді тільки і ламати знаходячи відповідну пару ВТ-ШТ, і знаходити ключ.
От тільки біда в тому що практично побудувати таку таблицю у нас час не можливо.

Почитайте краще про теоритичну стійкість шифрів, про обчислювальну стійкість.
Багато нового для себе дізнаєтесь.
Виявиться що всі сучасні шифри теоритично не стійкі, і всі це знають. :)

От тільки практично ви їх не зламаєте, з відомими методами криптоаналізу.
;)


Повернутися наверх
  
 
 Заголовок повідомлення: Re: RSA: будь який алгоритм шифрування є потенційно небезпеч
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 5
mathbilan писал(а):
На невеликих ключах, можливо знаходження абсолютно нових за ідеєю методів криптоаналізу.

Ви не змогли зробити криптоаналіз двозначних чисел, яка тоді цінність "алгоритму"?


Повернутися наверх
  
 
 Заголовок повідомлення: Re: RSA: будь який алгоритм шифрування є потенційно небезпеч
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
хочаб звідси не удаляйте тему :)


Повернутися наверх
  
 
 Заголовок повідомлення: Re: RSA: будь який алгоритм шифрування є потенційно небезпеч
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 5
mathbilan писал(а):
хоча б звідси не удаляйте тему :)

Не хвилюйтесь, тему видаляти ніхто не буде.
Не лусне форум. Всім місце знайдеться.

Будь хто може долучитись до дискусії, і хто знає, можливо через рік у когось виникне ідея.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: RSA: будь який алгоритм шифрування є потенційно небезпеч
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
Відповідь на пояснення Olgerd від 23 грудня 2013 року о 22:01.
По перше, нагадаємо основи теорії Дізьюнктивних Нормальних Форм (ДНФ).
Коньюнкт –(«НІ»х1)*х2*(«НІ»х3)*…*хn
Тобто це множення за допомогою «ТА» тверджень чи заперечень логічних змінних. При чому кожна змінна, будь вона твердженням, чи запереченням, зустрічається в коньюнкті тільки 1 раз. (Якщо коньюнкт одночасно містить і твердження, і заперечення однієї і тієї самої змінної, то він тотожно дорівнює нулю),
Деякі змінні у коньюнкті можуть бути відсутні.
ДНФ складається з логічної суми коньюнктів «АБО» (чи «+»).
Приклад ДНФ:
х1*(«НІ»х2)+х3+(«НІ»х4)*х1.
Правила додавання та множення двох ДНФ:
Додавання: ДНФ1+ДНФ2=ДНФ3
Коньюнкти ДНФ1 та ДНФ2записуються через «+» та викидається один з тих, що дублюється
Зауваження: число коньюнктів у ДНФ3<= арифметичній суммі кількості коньюнктів у ДНФ1 та ДНФ2.
Приклад:
ДНФ1=х1*х2+х2*(«НІ»х3)
ДНФ2=х1*х4+х2*(«НІ»х3)
ДНФ1+ДНФ2=ДНФ3= х1*х2+х2*(«НІ»х3)+ х1*х4
Множення двух ДНФ, у яких коньюнкти ДНФ1 містять змінні: (х1,х2,х3,…,хк
А у ДНФ2 коньюнкти містять змінні:(х(к+1),х(к+2),х(к+3),…,хn)
Тоді ДНФ3=ДНФ1*ДНФ2= логічній суммі логічних добутків кожного коньюнкта з ДНФ1 на кожен коньюнкт з ДНФ2.
Важливо:кількість коньюнктів у ДНФ3= арифметичному добутку кількості коньюнктів у ДНФ1 та ДНФ2.
Тобто перемножуючи h разів ДНФ-и, кожна з котрих містить 3 коньюнкта ми отримаємо 3^h коньюнктів на виході.
Тобто кількість розрахунків нас лякати не повинна
Наприклад: ДНФ1*ДНФ2*ДНФ3*… *ДНФh=ДНФf
Для прямого розрахунку ДНФf потрібно (3^h)*3*h операцій, а якщо обчислювати ДНФ1, потім ДНФ2, потім ДНФ3,… потім ДНФh, а потім перемножити, то всього 3*3*h=9*h
Тому велика таблиця, нас лякати не повинна, ми можемо обчислити її дуже економно:
Приєднання файлів:
Відповідь Olgerd.JPG [14.42 KiB]
Скачали: 0

До речі цитата з В.Задірака,О.Олексюк «Комп’ютерна криптологія» Київ 2002 стор. 148: «атака на окремі біти RSA дуже важка».


Повернутися наверх
  
 
 Заголовок повідомлення: Re: RSA: будь який алгоритм шифрування є потенційно небезпеч
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 282
Це все звісно цікаво, але Ви це застосуєте практично до вище згаданого прикладу? (Крім того що я уже описав 23 грудня)

Ви можете зламати RSA своїм методом швидше ніж повний перебір - ні.
Ви можливо("можливо" - так як доведення я не перевіряв) можете довести що RSA теоритично зламується? - Але це всі і так знають, як і про те що теоритично і AES-128 не стійкий, от тільки користі від цього мало.

mathbilan писал(а):
В.Задірака,О.Олексюк «Комп’ютерна криптологія» Київ 2002

От тут я Вас підтримую на всі 100% - а саме у тому що читаєте книги з криптографії. Почитайте і наш сайт. Почніть з класичної криптографії, подивіться приклади і т.д.


Повернутися наверх
  
 
Показати повідомлення за:  Сортувати по:  
Розпочати нову тему Відповісти  [ 18 повідомлень ] 

Часовий пояс: UTC десь + 2 години



cron
Роwеrеd bу рhрВB® аnd Hostinger web hosting