Як лінейны лічбавы аналіз можа зламаць крыптасістэму DES?

/ / Апублікавана ў кібербяспека, Асновы класічнай крыптаграфіі EITC/IS/CCF, Крыптасістэма шыфравання блокаў DES, Стандарт шыфравання дадзеных (DES) - расклад і расшыфроўка ключоў

Лінейны крыптааналіз - гэта магутны метад крыптааналітычнай атакі, які прымяняе лінейныя набліжэнні да дзеяння крыптаграфічнага алгарытму. Ён асабліва эфектыўны супраць блокавых шыфраў, такіх як стандарт шыфравання дадзеных (DES). Каб зразумець, як лінейны крыптааналіз можа зламаць крыптасістэму DES, вельмі важна разгледзець механіку як DES, так і прынцыпы лінейнага крыптааналізу.

1. Агляд DES:

Стандарт шыфравання дадзеных (DES) - гэта алгарытм з сіметрычным ключом для шыфравання лічбавых даных. Ён працуе з 64-бітнымі блокамі даных і выкарыстоўвае 56-бітны ключ. DES заснаваны на структуры Feistel, якая дзеліць ўваходны блок на дзве паловы і апрацоўвае іх праз некалькі этапаў перастаноўкі і замены. Кожны раўнд уключае наступныя этапы:
– Пашырэнне: правая палова блока пашырана з 32 біт да 48 біт.
– Змешванне клавіш: разгорнутая правая палова выконваецца XOR з дапамогай круглай клавішы, атрыманай ад асноўнай клавішы.
– Замена: вынік дзеліцца на восем 6-бітных сегментаў, кожны з якіх праходзіць праз адпаведны S-блок, ствараючы 4-бітны выхад.
– Перастаноўка: 32-бітны выхад з S-блокаў перастаўляецца ў адпаведнасці з загадзя вызначанай табліцай.

Затым левую і правую паловы мяняюць месцамі, і працэс паўтараецца на працягу 16 раундаў. Канчатковая перастаноўка дае зашыфраваны вынік.

2. Прынцыпы лінейнага крыптааналізу:

Лінейны крыптааналіз, распрацаваны Міцуру Мацуі ў пачатку 1990-х гадоў, накіраваны на выкарыстанне лінейных адносін паміж адкрытым тэкстам, зашыфраваным тэкстам і ключавымі бітамі. Асноўная ідэя складаецца ў тым, каб знайсці лінейныя набліжэнні, якія выконваюцца з пэўнай імавернасцю для нелінейных кампанентаў шыфра, такіх як S-блокі ў DES. Этапы лінейнага крыптааналізу наступныя:
– Вызначце лінейныя набліжэнні: вызначце лінейныя ўраўненні, якія набліжаюць паводзіны S-блокаў. Гэтыя набліжэнні выгляду P[i] \oplus C[j] \oplus K[k] = 0, Дзе P гэта біт адкрытага тэксту, C гэта біт зашыфраванага тэксту, і K гэта ключавы біт.
– Вылічыце зрушэнне: вымерайце верагоднасць захавання лінейнага набліжэння. Зрушэнне - гэта адхіленне ад 0.5 (верагоднасць таго, што выпадковая здагадка будзе правільнай).
– Збор даных: зашыфруйце вялікую колькасць адкрытых тэкстаў для збору дастатковых даных для статыстычнага аналізу.
– Аналіз даных: выкарыстоўвайце сабраныя даныя, каб вызначыць найбольш верагодныя ключавыя біты на аснове назіраных зрушэнняў.

3. Прымяненне лінейнага крыптааналізу да DES:

Прымяненне лінейнага крыптааналізу да DES ўключае некалькі этапаў. Давайце разбяром працэс:

3.1. Ідэнтыфікацыя лінейных набліжэнняў:

Першы крок - вызначыць лінейныя набліжэнні для S-скрыняў, якія выкарыстоўваюцца ў DES. Кожны S-блок у DES мае 6 уваходных і 4 выходных біта. Мэта складаецца ў тым, каб знайсці лінейныя ўраўненні, якія апраксімуюць выхады S-box з пэўным зрушэннем. Напрыклад, разгледзім S-box з уваходнымі бітамі x_1, x_2, x_3, x_4, x_5, x_6 і выхадныя біты у_1, у_2, у_3, у_4. Лінейнае набліжэнне можа мець выгляд:

    \[ x_1 \oplus x_2 \oplus y_3 = 0 \]

Гэта ўраўненне паказвае, што XOR ўваходных бітаў х_1 і х_2 і выхадны біт y_3 роўна 0 з пэўнай верагоднасцю.

3.2. Разлік зрушэння:

Пасля вызначэння лінейных набліжэнняў наступным крокам з'яўляецца вылічэнне зрушэння для кожнага набліжэння. Зрушэнне - гэта розніца паміж верагоднасцю захавання набліжэння і 0.5. Напрыклад, калі набліжэнне x_1 \oplus x_2 \oplus y_3 = 0 выконваецца з верагоднасцю 0.75, зрушэнне:

    \[ \эпсілон = 0.75 - 0.5 = 0.25 \]

3.3. Збор дадзеных:

Каб выканаць лінейны крыптааналіз на DES, патрабуецца вялікая колькасць пар адкрыты тэкст-зашыфраваны тэкст. Неабходная колькасць пар залежыць ад зрушэння лінейнага набліжэння. Як правіла, чым больш пар сабрана, тым вышэй дакладнасць аналізу. Для DES можа спатрэбіцца некалькі тысяч ці нават мільёнаў пар.

3.4. Аналіз дадзеных:

З дапамогай сабраных даных наступным крокам будзе аналіз пар адкрытага тэксту і зашыфраванага тэксту, каб вызначыць найбольш верагодныя біты ключа. Гэта ўключае ў сябе наступныя падэтапы:
– Для кожнай пары адкрыты тэкст-шыфраваны тэкст вылічыце значэнні лінейных набліжэнняў.
– Падлічыце, колькі разоў выконваецца кожнае набліжэнне.
– Выкарыстоўвайце падлікі, каб ацаніць верагоднасці і параўнаць іх з чаканымі верагоднасцямі на аснове зрушэнняў.

4. Прыклад лінейнага крыптааналізу на DES:

Разгледзім спрошчаны прыклад, дзе мы вызначылі лінейнае набліжэнне для першага S-блока ў DES. Выкажам здагадку, што набліжэнне:

    \[ P[1] \oplus C[3] \oplus K[5] = 0 \]

Тут, П[1] гэта першы біт адкрытага тэксту, C[3] з'яўляецца трэцім бітам зашыфраванага тэксту, і К[5] гэта пяты біт ключа. Крокі, каб зламаць DES з дапамогай гэтага набліжэння, наступныя:

4.1. Збор дадзеных:

Зашыфруйце вялікую колькасць адкрытых тэкстаў з дапамогай DES і збярыце адпаведныя зашыфраваныя тэксты. Для прастаты выкажам здагадку, што мы сабралі 1,000,000 XNUMX XNUMX пар адкрыты тэкст-зашыфраваны тэкст.

4.2. Аналіз дадзеных:

Для кожнай пары адкрыты тэкст-шыфраваны тэкст вылічыце значэнне P[1] \oplus C[3]. Калі вынік 0, павялічыць лічыльнік; у адваротным выпадку паменшыць лічыльнік. Значэнне лічыльніка пакажа зрушэнне набліжэння.

4.3. Ацэнка ключавых біт:

На падставе значэння лічыльніка ацаніце верагоднасць таго, што набліжэнне спраўджваецца. Параўнайце гэтую верагоднасць з чаканай верагоднасцю, заснаванай на зрушэнні. Калі назіраная верагоднасць значна вышэй або ніжэй за 0.5, гэта сведчыць аб тым, што ключавы біт К[5] хутчэй за ўсё будзе 0 або 1 адпаведна.

5. Практычныя меркаванні:

У той час як прыведзены вышэй прыклад спрошчаны, практычны лінейны крыптааналіз на DES уключае больш складаныя набліжэнні і некалькі S-блокаў. Акрамя таго, атака патрабуе значных вылічальных рэсурсаў для збору і аналізу даных. Аднак пры дастатковай колькасці дадзеных і вылічальнай магутнасці лінейны крыптааналіз можа эфектыўна скараціць прастору для ключоў і зрабіць магчымым аднаўленне ключа.

6. Контрамеры:

Для зніжэння рызыкі лінейнага крыптааналізу сучасныя крыптаграфічныя алгарытмы распрацаваны з улікам устойлівасці да такіх нападаў. Такія метады, як павелічэнне колькасці раундаў, выкарыстанне большага памеру ключа і ўключэнне больш складаных S-скрыняў, могуць павысіць бяспеку блокавых шыфраў. Для DES увядзенне Triple DES (3DES) забяспечвае больш высокі ўзровень бяспекі шляхам прымянення алгарытму DES тры разы з рознымі ключамі.

Іншыя апошнія пытанні і адказы адносна Стандарт шыфравання дадзеных (DES) - расклад і расшыфроўка ключоў:

Глядзіце дадатковыя пытанні і адказы ў Стандарт шыфравання дадзеных (DES) - Расклад і дэшыфраванне ключоў

Яшчэ пытанні і адказы:

тэгі: , , , , ,