Спосіб криптографічного перетворення інформації з використанням каскадних кодів

Спосіб криптографічного перетворення інформації з використанням каскадних кодів, який полягає в тому, що інформаційні дані перетворюються у криптограму (кодове слово, яке маскується під випадкову послідовність) за допомогою пристроїв кодування замаскованого лінійного блокового коду, який відрізняється тим, що при перетворенні інформаційних даних як закритий ключ для маскування коду використовують породжувальні матриці m+1 групових кодів другого рівня узагальненого каскадного коду порядку m. (19) (21) u200803483 (22) 18.03.2008 (24) 26.08.2008 (46) 26.08.2008, Бюл.№ 16, 2008 р. (72) СТАСЄВ ЮРІЙ ВОЛОДИМИРОВИЧ, UA, КУЗНЄЦОВ ОЛЕКСАНДР ОЛЕКСАНДРОВИЧ, U A, ГРАБЧАК ВОЛОДИ МИР ІВАНОВИЧ, U A, ЄВСЕЄВ СЕРГІЙ ПЕТРОВИЧ, UA, КОРОЛЬОВ РОМАН ВОЛОДИМИРОВИЧ, UA, ЧОПЕНКО ДМИТРО АНАТОЛІЙОВИЧ, U A (73) ХАРКІВСЬКИЙ УНІВЕРСИТЕТ ПОВІТРЯНИХ СИЛ ІМЕНІ ІВАНА КОЖЕДУБА, U A 3 34853 Технічний результат, який може бути отриманий при здійснені корисної моделі полягає в надійному маскуванні коду та значному спрощенні реалізації алгоритмів криптографічного перетворення за допомогою кодів. На фіг. подано геометричне трактування узагальненого каскадного коду. Початковими даними для опису узагальненого каскадного коду є двійкове слово с довжини n=n1n2, яке представляється у вигляді послідовності двійкових векторів С j, j = 1 n2 , довжини n1, тоб, то: ( ) c = c1 , c 2 ,..., c n 1 , c n +1,..., c 2n 1 , c 2 n1 + 1,..., c n 2 n 1 = ( ( ) ( = (C1, C2 ,..., Cn ) C j = (c (j -1)n + 1,..., c jn ), , )) = (c 1, c 2 ,..., c n1 ), c n + 1,..., c 2 n 1 , ..., c 2n 1 + 1,..., c n 2 n 1 = (1) 2 1 1 j де n2 квадратних двійкових матриць H0 , j = 1 n2 , порядку n1; , m+1 групових над GF( 2a i ), i = 1, m + 1 , кодів (кодів другого рівня) з параметрами (n2, bi, d2i). При цьому виконується рівність m +1 å a1 = n1 . (2) i =1 У основному варіанті побудови узагальнених j каскадних кодів як матриці H0 для всіх j = 1 n2 , вибирається одна і та ж трикутна матриця Н 0 порядку n1, яка в клітковій формі має вигляд Ia1 P11 Ia 2 0 P21 P22 Ia 3 H0 = , (3) ... ... ... ... ... ... Pm1 Pm2 Pm3 ... Pmm I am +1 ~ Hi = Pi 1 Pi 2 ... Pii Ia 1 0 ... 0 , i = 1 m , (4) , де клітки Pi s - двійкові матриці розмірів ai+1хаs, Ias - одинична матриця порядку а s . Перевірочна матриця Нi, вигляду ~ Hi Pi1 ~ Pi +11 H Hi = i+1 = ... ... ~ Pm1 Hm Pi 2 Pi+ 12 ... Pm2 ... Pii ... Pi+ 1i ... ... ... Pm i Ia i+ 1 Pi +1i +1 ... Pm i+1 0 Ia i+ 2 ... ... ... Pmm ... Ia m+1 i = 1, m , (5) 4 ( Двійкове слово с довжини n=n1n2 є кодовим словом узагальненого каскадного коду порядку m тоді і тільки тоді, коли всі пов'язані із словом с вектори γi, i = 1, m + 1 , є кодовими словами відповідних (і-х) кодів другого ступеня. Величини аi>0 і bi≥0, що визначають внутрішню стр уктур у узагальненого каскадного (n,k,d) коду, вибираються довільно, при цьому (n,k,d) параметри задовольняють наступним співвідношенням: n=n1n2; (7) m +1 k = å aibi ; (8) i =1 ( ) C jHT = g 1j , g 2 j,..., g m+ 1j , j = 1 n2 . (6) , 0 де γij - двійковий вектор довжини аi. Трактуючи вектори γij як елементи поля GF( 2a i ), складемо з цих елементів, в результаті відображення (6) (для кожного слова с), вектори { { } ìmin d 1i d 2i : i = 1 m при b m+1 = 0, , ï d³í (9) ïmin d 2m +1, d1i d2i : i = 1, m при b m+1 ¹ 0 . î } Сутність запропонованого способу криптографічного перетворення інформації з використанням каскадних кодів полягає в тому, що інформаційні данні перетворюються у криптограму(кодове слово яке маскується під випадкову послідовність ) за допомогою пристроїв кодування замаскованого лінійного блокового коду. При перетворенні інформаційних даних, породжувальні матриці Gi m+1 a групових над GF( 2 i ), i = 1, m + 1 кодів (кодів другого рівня) з параметрами (n2,bi,d2i) узагальненого каскадного коду маскуються невиродженими матa рицями Xj розміру bixbi з елементами із GF( 2 i ) та використовуються як закритий ключ. Інформаційні данні шляхом поетапного ітеративного оброблювання кожним із кодів першого та другого рівнів узагальненого коду перетворюються у криптограму (кодове слово що замасковане під випадкову послідовність) за допомогою відповідних пристроїв кодування. Матриці Хі та розклад числа n1 у відповідну послідовність аі, i = 1, m + 1 за правилом (2) зберігається в секреті, тобто використовують у якості секретного ключа. Якщо значення порядку т узагальненого каскадного коду також зберігається в секреті, число різних варіантів вибору ступеня розширення полів GF( 2a i ) для побудови кодів другого ступеня визначається виразом 0 v = Cn 1 повністю визначувана матрицею Н 0 (складається з m - і + 1 клітинних рядків матриці Н0) задає i-й код першого рівня з параметрами (n1,ki,d1i), при цьому для числа інформаційних символів i-го коду виконується співвідношення ki=a1+а2+...+a i;. Зафіксуємо лінійне відображення векторів С j ) gi = g i1, gi2 , ..., g in 2 , i = 1, m + 1 . -1 + C1 n 1 -1 + C2 n 1 n 1 -1 -1 j + ... + C n1 - 1 = å C n n -1 1 j=0 1 -1 = 2n 1 -1 . (10) При відомому значенні m число різних варіантів вибору відповідних ступенів розширення полів a GF( 2 i ) визначається значенням біноміального коефіцієнта, тобто v = Cm+ 1 . (11) n -1 1 Для кожного із зазначених варіантів для злому ключа потрібно перебрати всі можливі матриці Х*і, i = 1, m + 1 що можуть бути використані у якості відповідних матриць Xi. Таким чином при належних n1 і m використання запропонованого способу дозволяє надійно замаскувати код. Крім того, для кодування узагальненим каскадним кодом методом 5 34853 множення матриць у загальному випадку потрібно виконати: - для всіх кодів зовнішнього рівня m +1 n1 × å bi i =1 операцій множення та додавання над полями GF( 2a i ); - для всіх кодів внутрішнього рівня m i i =1 j=1 å n 2 × å ai операцій множення та додавання над двійко Комп’ютерна в ерстка Д. Шев ерун 6 вими елементами, що при врахуванні співвідношень (7)-(9) значно менш ніж у найближчому аналозі. Джерела інформації: 1. R.J. McEliece. A Public-Key Criptosystem Based on Algebraic Theory. // DGN Progres Report 42-44, Jet Propuisi on Lab. Pasadena, CA. January February, 1978. - P. 114-116. 2. T.R.N. Rao and K.H. Nam, "Private-key algebraic-coded cryptosystem", in Advances in Cryptology-CRYPTO 86. New York, NY: Springer, 1986. - P. 35-48. Підписне Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601