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

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

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




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

Повідомлень: 502
Частотний криптоаналіз - метод криптоаналізу шифрів простої підстановки, який грунтується на нерівномірності повторюваності букв на письмі.

Наприклад, для англійської мови, найчастіше зустрічаються в тексті літери "t" та "e".


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

Повідомлень: 502
Наприклад, для середньостатичного україномовного тексту отримаємо послідовність:
(він найчастіше вживаних, до наймаменш вживаних літер):
Код:
#ASCII код - "літера"

#32     "   "
#238     " о "
#237     " н "
#224     " а "
#179     " і "
#232     " и "
#242     " т "
#226     " в "
#240     " р "
#229     " е "
#241     " с "
#234     " к "
#228     " д "
#235     " л "
#243     " у "
#236     " м "
#239     " п "
#255     " я "
#231     " з "
#252     " ь "
#225     " б "
#44     " , "
#227     " г "
#245     " х "
#46     " . "
#247     " ч "
#13       
#233     " й "
#246     " ц "
#254     " ю "
#230     " ж "
#191     " ї "
#186     " є "
#10       
#248     " ш "
#244     " ф "
#249     " щ "



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

Повідомлень: 502
Але проблема в тому що для різних текстів ця послідовність буде дещо змінюватись.
Наприклад, для головної сторінки форуму:

Код:
#32    "   "
#238    " о "
#224    " а "
#226    " в "
#232    " и "
#237    " н "
#179    " і "
#242    " т "
#229    " е "
#240    " р "
#241    " с "
#235    " л "
#236    " м "
#243    " у "
#234    " к "
#228    " д "
#239    " п "
#252    " ь "
#231    " з "
#255    " я "
#44    " , "
#227    " г "
#225    " б "
#46    " . "
#233    " й "
#247    " ч "
#230    " ж "
#245    " х "
#248    " ш "
#254    " ю "
#246    " ц "
#191    " ї "


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

Повідомлень: 502
Код:
#32     "   "
#238     " о "
#237     " н "
#224     " а "

<>
Код:
#32    "   "
#238    " о "
#224    " а "
#226    " в "

Нам вдалось визначити тільки пробіл та літеру "о", та близько літеру "а".

Що ж робити далі?


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

Повідомлень: 502
Як правило не використовують одну послідовність.
Використовують декілька еталонних послідовностей, перевіряючи кожну, починаючи з найбільш імовірної.

Тобто по можливості необхідно знати тему повідомлення.
Як правило це визначається по аналізу - хто, кому, коли , за яких обставин відправив повідомленя.


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

Повідомлень: 502
Для прикладу, розглянемо зашифрований вірш Т.Г.Шевченка,
після підстановки за допомогою еталоної послідовності отримаємо:
Цитата:
домонруа члпахнас еткоядо домонруас еткоядос коядо лпоя звігами етвілуа їіпяонруа. етвілуас вілуа ва яизоьуа. етзвіги біуінрюв,еткрки уіжав,с а нак ними етмодиуи зинрюв,. етва шо б водос шо яизолретнрьво хь ні бнайс етнрьво шипо ні багуаїіс етнрьво
о ні бдакай. етвру,ло ярвіп виьізін,ло етгоярй нак нимис етвру,ло пози панізін,ло етзу,обами кпрцними етхь чмиюв,. бр кі зоніс етозчив,с гпидпрйета чнчли хм ца кчжіс етганам живо зрюв,. етцадаво хьс а ьво злажіс еткі онви модиуас етмчїінила гпаяіккнодо еткі гоьопониуиеткі баурбнлс кча шипас еткі окгоїияайетвжло яажло лав ганчйс ета хь ні бдакаюв,.ет


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

Повідомлень: 502
Знайдемо слова які читаються.
Знайшли:
"ними"
у рядку:
"а нак ними етмодиуи"
схоже на "а над ними".
Замінюємо д на к.

Бачимо що закінчення "уа" повторюється часто.
Такого закінчення нема в українській мові, отже там або "та","на","ва","ла"...

припустімо "та".
Не знаходми слів, що читаються.
Тоді припустимо що "ва" ("на" не може бути, так як літера "н" уже викростана у фразі "а над ними")
Знову не знаходимо.
Тоді, "ла".

Знаходимо
"а жто" - отже "а хто"
Отже ми уже знаємо літеру о та т.

Знаходимо слово
"мокила"
схоже на "могила".

"дояго" ="довго"
Знаємо літеру в.

"визохла"="висохла"
Дізнались літеру "с".

Перше слово
"гомонрла" ="гомоніла"
Знайшли літеру "і".

і т.д.

В резульататі отримаємо:
Цитата:
гомоніла україна,
довго гомоніла,
довго, довго кров степами
текла-червоніла.
текла, текла та й висохла.
степи зеленіють
діди лежать, а над ними
могили синіють.
та що з того, що високі
ніхто їх не знає,
ніхто щиро не заплаче,
ніхто не згадає.


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

Повідомлень: 502
Ефективність даного методу залежить від довжиши шифртексту.
Оптимально, щоб шифртекст був не менше 1-2кБ.

Клод Шенон ввід термін "період єдиності" - мінімальна довжина шифр тексту для певної мови, коли шифртекст можливо однозначно розшифрувати.

Для англійської мови він складає 26 знаків, для української 32.

Тобто це значить, що для тексту довжниою менше періоду єдиності, можна знайти декілька варіантів розшифровки.
Наприклад,
шифр текст
Код:
22 32 14 29

може бути зашифроване будь-яке слово з 4-х літер, літери якого не повторюються, тобто "літо","сніг","вона" тощо.


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

Повідомлень: 362
Назва "частоний аналіз" також поширюється на методи частотного аналізу біграм, триграм і т.д. (сполучень 2-х,3-х,4-х і т.д. літер).

Принцип той же як і для аналізу букв, тільки використовуються таблиці біграм, триграм і т.д.



Наприклад, поширені біграми української мови:
Код:
на
но
ст
ов
ко
ро
ни
ер
ан
ом
пр



поширені біграми англійської мови
Код:
th
he
er
in
an
re
nd
at
on
es
ha
nt
en
st
ed
to
it
ou
ea
hi
is


Для російської мови:
Код:
ст
то
но
на
по
ен
ни
ко
ра
ов
не
ро
пр
ал
го
ре
ос
ли
ка
во
ер
та
от
ва
ор
ол
ет
те
ом
ан
ел
од
ть


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

Повідомлень: 362
Метод хі-квадрат.

За допомогою частотного аналізу проводять χ2 (хі-квадрат) аналіз:

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

Обчислюється за формулою

χ2(Pc,Pp) = Σ ((Pci-Ppi)^2/Ppi)

де
Pp - ймовірності еталонної послідовності,
Pc - ймовірності повторюваності літер шифротексту.


Востаннє редагувалось Raul в 28 лют 2013, 15:44, всього редагувалось 3 разів.

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

Повідомлень: 362
Метод коефіцієнта кореляції.

За допомогою частотного аналізу проводять кореляційний аналіз:

тобто також перевіряють розбіжність таблиці еталонної повторюваності букв з повторюваністю літер шифротексту.
Чим ближче до 1 тим більше вони співпадають.

Лінійна кореляця обчислюється за формулою

r(x,y) = Σ ((xi-xсер)*(yi-yсер)) / корінь_квадратний( Σ ((xi-xсер)^2*(yi-yсер)^2) )

Де
x,y - характеристики відкритого та зашифрованого тексту.


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

Повідомлень: 282
Для літер англійського алфавіту, частота у порядку спадання:
Код:
01   e
02   t
03   a
04   o
05   i
06   n
07   s
08   h
09   r
10   d
11   l
12   c
13   u
14   m
15   w
16   f
17   g
18   y
19   p
20   b
21   v
22   k
23   j
24   x
25   q
26   z


Найбільш часто зустрічається літера "e".


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

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



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