Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования
Pre-conditions of account of structural features of prime numbers are
 grounded at the decision of task of factorization. It is assumed that by offered approach it is possible to organize an attack on shifrotekst, calculable complication of which will be below exponential.
Збережено в:
| Опубліковано в: : | Моделювання та інформаційні технології |
|---|---|
| Дата: | 2009 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2009
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/29643 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования / В.В. Мохор, А.В. Жилин // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 52. — Бібліогр.: 3 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860238026579378176 |
|---|---|
| author | Мохор, В.В. Жилин, А.В. |
| author_facet | Мохор, В.В. Жилин, А.В. |
| citation_txt | Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования / В.В. Мохор, А.В. Жилин // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 52. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| container_title | Моделювання та інформаційні технології |
| description | Pre-conditions of account of structural features of prime numbers are
grounded at the decision of task of factorization. It is assumed that by offered approach it is possible to organize an attack on shifrotekst, calculable complication of which will be below exponential.
|
| first_indexed | 2025-12-07T18:26:16Z |
| format | Article |
| fulltext |
УДК 511.215
Мохор В.В., д.т.н., профессор, ИССЗИ НТУУ “КПИ”, Киев
Жилин А.В. ИССЗИ НТУУ “КПИ”, Киев
ПРЕДПОСЫЛКИ УЧЕТА СТРУКТУРНЫХ ОСОБЕННОСТЕЙ
ПРОСТЫХ ЧИСЕЛ ПРИ РЕШЕНИИ ЗАДАЧИ ФАКТОРИЗАЦИИ В
КОНТЕКСТЕ ПОСТРОЕНИЯ АТАКИ НА ШИФРОТЕКСТ, КОТОРЫЙ
ЗАШИФРОВАН АСИММЕТРИЧНЫМ МЕТОДОМ ШИФРОВАНИЯ.
Pre-conditions of account of structural features of prime numbers are
grounded at the decision of task of factorization. It is assumed that by offered
approach it is possible to organize an attack on shifrotekst, calculable
complication of which will be below exponential.
Асимметрические методы шифрование широко используются в наше
время. Их популярность основана на том, что они решают проблему передачи
секретного ключа. На основе этих методов построены многие алгоритмы
шифрования, самый известный и широко применяемый из них это RSA.
Стойкость этого алгоритма основана на трудоемкости разложения на
множители (факторизации) больших чисел [2].
В общем случае вычислительная сложность процесса факторизации
имеет экспоненциальный характер [3]. Оценка сложности обусловлена
числом переборов возможных вариантов простого числа в двоичной форме
на интервале:
n2..1 , (1)
где n – разрядность факторизируемого числа
Количество таких простых чисел на интервале определяется формулой
Чебышёва [1]:
)ln(
)(
a
aa , (2)
где a - простое число.
Применяя ограничение (1) к формуле (2) имеем верхнюю границу
оценки сложности процесса факторизации:
2ln
2
)2ln(
2)(
1
2
n
nO
n
n
n
h (3)
Если представить случай факторизации, реализованный определенным
способом, который будет иметь вычислительную сложность ниже
экспоненциальной, то можно будет утверждать, что в общем случае процесс
факторизации также будет имеет вычислительную сложность ниже
экспоненциальной.
Представим факторизируемое число в двоичной форме
nzzzzZ ...210 , где 0z - старший разряд числа, nz - младший разряд
числа. Оно является произведением двух простых чисел
kxxxxxX ...4321 и kyyyyyY ...4321 , где 11 , yx - старшие
разряды, kk yx , - младшие разряды чисел X и Y соответственно:
YXZ * .
2)1(1010 /n...k,k...n,j,i,,y,xz jji
Умножим число X на Y , которые имеют по 5 разрядов ( 54321 xxxxx и
54321 yyyyy ) согласно правилам умножения чисел:
1x 2x 3x 4x 5x
1y 2y 3y 4y 5y
5y 1x 5y 2x 5y 3x 5y 4x 5y 5x
4y 1x 4y 2x 4y 3x 4y 4x 4y 5x
3y 1x 3y 2x 3y 3x 3y 4x 3y 5x
2y 1x 2y 2x 2y 3x 2y 4x 2y 5x
1y 1x 1y 2x 1y 3x 1y 4x 1y 5x
0z 1z 2z 3z 4z 5z 6z 7z 8z 9z
Основываясь на этих правилах, получаем приведенную ниже систему
уравнений:
10 1,0 Pz
2111 Pxyz
312212 Pxyxyz
41322313 Pxyxyxyz
5142332414 Pxyxyxyxyz
615243342515 Pxyxyxyxyxyz
7253443526 Pxyxyxyxyz (4)
83544537 Pxyxyxyz
45548 xyxyz
559 xyz
где tP - разрядный перенос.
Определим, что система в заданном виде будет иметь старшие и
младшие разрядные уравнения. Старшинство уравнений определяется между
ними в соответствии тому, к какому разряду факторизируемого числа оно
приравнивается. Вследствие этого tP будет представлять собой разрядный
перенос с младшего разрядного уравнения. Он выражает возможное
количество единиц, которые могут быть перенесены.
Необходимо заметить, что последние разряды чисел X и Y всегда равны
1 ( 5y , 5x =1), так как эти числа простые, а простые числа нечетные и в
двоичной системе счисления заканчиваются на единицу (кроме числа 2, но
согласно условия берутся большие простые числа). 0z будет принимать
однозначное значение 0 или 1 (зависит от значения составных чисел).
Возьмем частный случай, когда числа X и Y равны между собой. Тогда
разряды этих чисел, представленных в двоичной форме, также равны между
собой. Исходя из этого, получаем систему уравнений вида:
10 1,0 Pz
2111 Pxxz
312212 Pxxxxz
41322313 Pxxxxxxz
5142332414 Pxxxxxxxxz
615243342515 Pxxxxxxxxxxz (5)
7253443526 Pxxxxxxxxz
83544537 Pxxxxxxz
45548 xxxxz
559 xxz
Применим к системе следующие правила:
iii xxx
0 ii xx с переносом ix в старший разряд. (6)
Они основываются на Булевой алгебре и правиле умножения чисел в
столбик. Используя эти правила, получаем следующую систему уравнений:
10 1,0 Pz
21211 Pxxxz
3132 Pxxz
4142323 Pxxxxxz
52414 Pxxxz
634325 Pxxxxz (7)
436 xxz
07 z
08 z
19 z
Возьмем число Z , значение которого будет равно 10 0001 0001.
Подставим данное значение в систему уравнений и решим ее. Разрядный
перенос уберем из исходного уравнения, находя его по ходу решения
системы, используя для этого правила (6). Для удобства рассмотрения
системы пронумеруем ее уравнения. Исходная система уравнений будет
иметь вид:
11:0 P
1210:1 xxx
130:2 xx
142320:3 xxxxx
2410:4 xxx
34321:5 xxxx (8)
430:6 xx
00:7
00:8
11:9
Решить данную систему возможно путем выражения неизвестных друг
через друга и подстановку их в систему уравнений.
В (6) уравнении выразим 3x через 4x :
43 xx (9)
Подставим данную зависимость в систему уравнений (8).
11:0 P
1210:1 xxx
140:2 xx
142420:3 xxxxx
2410:4 xxx
44421:5 xxxx (10)
440:6 xx
00:7
00:8
11:9
Основываясь на правилах (6) получим:
11:0 P
1210:1 xxx
140:2 xx
142420:3 xxxxx
42410:4 xxxx
421:5 xx (11)
00:6
00:7
00:8
11:9
Обратим внимание на то, что в системе (10) шестая строка имела вид
440:6 xx . Основываясь на правилах (6) получился разрядный перенос
разряда 4x с шестого разрядного уравнения на пятое, что учитывает
вероятность наличия переносов в системе, которые полностью зависят от
значений разрядного уравнения, с которого делается перенос.
В 5 уравнении выразим 2x через 4x :
)1( 42 xx (12)
Подставим данную зависимость в систему уравнений (11).
11:0 P
141 )1(0:1 xxx
140:2 xx
14444 )1()1(0:3 xxxxx
4441 )1(0:4 xxxx
44 )1(1:5 xx (13)
00:6
00:7
00:8
11:9
Упростим систему (13):
11:0 P
141 )1(0:1 xxx
140:2 xx
14410:3 xxx
410:4 xx
11:5 (14)
00:6
00:7
00:8
11:9
В 4 уравнении выразим 1x через 4x :
41 xx (15)
Подставим данную зависимость в систему уравнений (14).
11:0 P
444 )1(0:1 xxx
440:2 xx
44410:3 xxx
440:4 xx
11:5 (16)
00:6
00:7
00:8
11:9
Основываясь на правилах (6) получим:
11:0 P
40:1 x
40:2 x
410:3 x
00:4
11:5 (17)
00:6
00:7
00:8
11:9
Анализируя систему уравнений (17) можно сделать выводы, что
14 x . Подставим полученное значение равенства в равенства (15), (12) и
(9):
141 xx (18)
011)1( 42 xx (19)
143 xx (20)
Согласно условия 5x =1. Число X принимает вид:
10225432110 2310111 xxxxxX
Возведя в квадрат вычисленный результат, получим заданное условием
значение числа Z , что подтверждает правильность решения системы
уравнений.
В общем виде система уравнений при равных числах X и Y будет иметь
вид:
}1,0{0 z
1211 xxxz
132 xxz
142323 xxxxxz
………………………………
1345 nnnk xxxz
21324 nnnnk xxxxz (21)
123 nnk xxz
02 kz
01 kz
1kz ,
где k – разрядность факторизируемого числа, а n – разрядность простого
числа. Представим алгоритм построения этой системы, записанный
формальным языком программирования:
m:=0: i:=1:
для j от 1 до n делать1 Mas[m+2,1]:=X[j]*X[j]:
пока i+j<=n делать2 Mas[m+i+1,j+1]:=X[j]*X[i+j]: i:=i+1 конец2:
m:=m+2: i:=1
конец1
для i от 1 до 2*n делать1 Mas[i,n+1]:=Z[i] конец1
где Mas[ ] – массив, который определяет структуру системы уравнений
вида (21).
Обобщая приведенный порядок действий над системой уравнений,
можем представить алгоритм нахождения разрядов простого числа:
1. Основываясь на значении факторизируемого числа,
представляем систему уравнений вида (21).
2. Выражаем некоторый старший разряд ix в ойq строке
через младший и разряд факторизируемого числа.
3. Подставляем ix в систему уравнений.
4. Упрощаем систему, используя правила (6).
5. Шаги 2-4 проделываем до строки под номером 2)1( n .
В итоге получается система с одним неизвестным 1kx . Из вида
системы делаем вывод, чему равен 1kx . Подставляем полученное значение
в выражения, которые были получены на втором шаге алгоритма. Вычисляем
значения всех неизвестных разрядов простого числа.
Рассмотрим систему (7) начиная с младших разрядных уравнений.
Последние три разряда факторизируемого числа всегда будут иметь
однозначное значение 001, так как это определено структурой системы
уравнений, которую определяют множители.
Строка 6 имеет вид 436 xxz . Можно утверждать, что 3x зависит
от 46 , xz . Это можно записать как:
),( 643 zxfx (22)
Применяя те же изыскания и основываясь на проведенных вычислениях,
можно утверждать что:
),,,( 65432 Pzxxfx (23)
),,,( 54421 Pzxxfx (24)
Рассмотрим разрядные переносы 6P и 5P . Они, как и другие в системе
уравнений такого типа, выражают возможное количество единиц, которые
могут быть перенесены с младшей разрядной строки. Вследствие этого они
полностью зависят от неизвестных, которые и формируют значения
переносов. Значит можно утверждать, что
),,( 6436 zxxfP (25)
),,,,( 654325 PzxxxfP
),,,,( 65432 zzxxxf (26)
Как видно из зависимости (26), переносы в старшем разрядном
уравнении определенно зависят от неизвестных, которые определяются в
нижних разрядных уравнениях и которые предопределяются за условием
),( 65 zz .
В зависимости (23) имеем ),,,( 65432 Pzxxfx . Основываясь на
утверждениях (22) и (25) можно записать:
)),(,,),,(( 6,4354642 zxxfzxzxffx
))),,((,,),,(( 6,46454642 zxzxffzxzxffx
),,( 6542 zzxfx (27)
Равность (27) показывает, что 2x зависит от возможных вариантов
действий над 654 ,, zzx . Т.е. 2x однозначно определяется через 654 ,, zzx .
В зависимости (22) имеем ),,,( 54421 Pzxxfx . Основываясь на
утверждениях (27), (26) и (22) можно записать:
)),,,,(,,),,,(( 65432446541 zzxxxfzxzzxffx
),,,((,,),,,(( 654446541 zzxffzxzzxffx )),,),,( 65464 zzxzxf
),,,( 65441 zzzxfx (28)
Равность (28) показывает, что 1x зависит от возможных вариантов
действий над 6544 ,,, zzzx . Т.е. 1x однозначно определяется через
6544 ,,, zzzx .
Проанализировав приведенные утверждения, и проведя аналитические
исследования зависимостей значений разрядов простых чисел друг от друга и
от значений разрядов факторизируемого числа, основываясь на системе
уравнений вида (21) и ее алгоритме построения, можно привести
обобщенные выводы.
Обозначим:
k – разрядность простого числа
ix – разряд простого числа
kixX i ...1|}{ – множество значений разрядов простого числа.
nqzZ q ...0|}{ – множество значений разрядов факторизируемого
числа
1...1|}{ nlPP l – множество значений переносов
{}{}{}},,{ PZXPzxXZ lqi
{}{} XZX i
{})( ii Xfx - ix зависит от элементов множества {}iX
Вывод зависимостей значений разрядов простых чисел друг от друга и
от значений разрядов факторизируемого числа приобретает вид:
2...1 ki
если i нечетное, то }),,{( 1 qqjii PzxXfx ,
где 4...2,1...1 nikqkij
если i четное, то }),,{( 1 qqjii PzxXfx ,
где 4...2,2/)(,1...1 nikqinjkij если 2 ki ,
то }),{( qjii zxXfx ,
где iq 2 .
Раскрывая зависимости, приходим к утверждению:
}),{( 1 qkii zxXfx , (29)
где 42...23...1
2
1
kikninq .
С утверждения (29) видно, что любой разряд простого числа однозначно
зависит от возможных вариантов действий над предпоследним разрядом
этого же простого числа и разрядами числа, которое факторизируется. Это
дает право утверждать, что возможно математическое выражение любого
разряда простого числа от предыдущих и от значений разрядов
факторизируемого числа.
Так как на каждом шаге данного алгоритма имеет место выражение
неизвестной и подстановку ее в каждое разрядное уравнение, то
вычислительная сложность алгоритма будет равна:
2)( kkO (30)
Формула (30) показывает нижнюю границу процесса факторизации,
который сведен к частному случаю, когда простые числа равны между собой.
Представленная зависимость (29), алгоритм и его вычислительная
сложность (30) дают основания предполагать, что в общем случае процесс
факторизации может иметь вычислительную сложность ниже
экспоненциальной. Значит, учитывая структурные особенности простых
чисел при решении задачи факторизации, можно организовать атаку на
шифротекст, который зашифрован асимметричным методом шифрования, и
вычислительная сложность данной атаки будет ниже экспоненциальной.
Также представленный алгоритм программно реализован с помощью
программного пакета символьных вычислений Maple. В качестве
эксперимента было вычислено значения 3030 простых чисел, имея в качестве
входных данных их квадраты. В ходе эксперимента не было ни одного
неправильного решения, что подтверждает правильность приведенных выше
выводов.
1. Ингам А.Е. Распределение простых чисел. – М: 1936 – 159с.
2. Шнайер Б. Прикладная криптография. – М.: Издательство ТРИУМФ,
2003 – 816 с.: ил.
3. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. —
М.:МЦНМО, 2003.—328 с.
|
| id | nasplib_isofts_kiev_ua-123456789-29643 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0068 |
| language | Russian |
| last_indexed | 2025-12-07T18:26:16Z |
| publishDate | 2009 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Мохор, В.В. Жилин, А.В. 2011-12-25T00:12:48Z 2011-12-25T00:12:48Z 2009 Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования / В.В. Мохор, А.В. Жилин // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 52. — Бібліогр.: 3 назв. — рос. XXXX-0068 https://nasplib.isofts.kiev.ua/handle/123456789/29643 511.215 Pre-conditions of account of structural features of prime numbers are
 grounded at the decision of task of factorization. It is assumed that by offered approach it is possible to organize an attack on shifrotekst, calculable complication of which will be below exponential. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Моделювання та інформаційні технології Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования Article published earlier |
| spellingShingle | Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования Мохор, В.В. Жилин, А.В. |
| title | Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования |
| title_full | Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования |
| title_fullStr | Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования |
| title_full_unstemmed | Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования |
| title_short | Предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования |
| title_sort | предпосылки учета структурных особенностей простых чисел при решении задачи факторизации в контексте построения атаки на шифротекст, который зашифрован асимметричным методом шифрования |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/29643 |
| work_keys_str_mv | AT mohorvv predposylkiučetastrukturnyhosobennosteiprostyhčiselprirešeniizadačifaktorizaciivkontekstepostroeniâatakinašifrotekstkotoryizašifrovanasimmetričnymmetodomšifrovaniâ AT žilinav predposylkiučetastrukturnyhosobennosteiprostyhčiselprirešeniizadačifaktorizaciivkontekstepostroeniâatakinašifrotekstkotoryizašifrovanasimmetričnymmetodomšifrovaniâ |