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

Частотний криптоаналіз
http://crprogram.16mb.com/topic-t89.html
Сторінка 1 з 1

Автор:  Tariq [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Частотний криптоаналіз

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

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

Автор:  Tariq [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

Наприклад, для середньостатичного україномовного тексту отримаємо послідовність:
(він найчастіше вживаних, до наймаменш вживаних літер):
Код:
#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     " щ "


Автор:  Tariq [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

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

Код:
#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    " ї "

Автор:  Tariq [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

Код:
#32     "   "
#238     " о "
#237     " н "
#224     " а "

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

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

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

Автор:  Tariq [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

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

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

Автор:  Tariq [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

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

Автор:  Tariq [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

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

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

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

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

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

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

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

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

і т.д.

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

Автор:  Tariq [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

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

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

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

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

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

Автор:  Raul [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

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

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



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



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


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

Автор:  Raul [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

Метод хі-квадрат.

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

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

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

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

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

Автор:  Raul [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

Метод коефіцієнта кореляції.

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

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

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

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

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

Автор:  Hazo [ 09 гру 2014, 20:48 ]
Заголовок повідомлення:  Re: Частотний криптоаналіз

Для літер англійського алфавіту, частота у порядку спадання:
Код:
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".

Сторінка 1 з 1 Часовий пояс: UTC десь + 2 години
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/