Современная прикладная криптография (стр. 19 )

Например,

D=231(768 бит) , Y = 2010;

D=309(1024 бит), Y = 2018.

При Y=2006 получается D=200 (665 бит).

1988. Поллард нашел новый подход для факторизации целых чисел. H. Lenstra развил его для чисел специального вида. Далее рядом авторов он был распространен на произвольные числа со сложностью L[1/3, c], где с=(64/9) = 1,9229… .

L[t, c] = exp((c+0(1))((logN))(loglogN)).

Далее Копперсмит улучшил оценку для с=1,9018… .(См. Modifications to the Number Field Sieve, J. Cryptology 6(1993),169-180)

Задача RSA

Дано: модуль N=pq, открытая экспонента e, шифрованный текст C=M(mod N).

Найти: открытый текст M.

Гибкая (flexible)задача RSA. Сильная задача RSA (пер. книги В. Мао)

Дано: модуль N=pq, шифрованный текст C=M(mod N), полученный при некоторой неизвестной открытой экспоненте e.

Найти: пару e` и M`, удовлетворяющую соотношению (M`)(mod N) = C.

Задача RSA с малой открытой экспонентой (low-exponent RSA problem)

On the Equivalence of RSA and Factoring Regarding Generic Ring Algorithms(Об эквивалентности задачи RSA и факторизации в классе общих кольцевых алгоритмов)

Gregor Leander, Andy Rupp

Статья посвящена известной достаточно старой проблеме вычислительной эквивалентности задачи вскрытия схемы RSA (задача RSA) и задачи факторизации (разложения) больших целых чисел (модуля схемы RSA).

Показано, что любой эффективный общий (generic) алгоритм, учитывающий структуру кольца Z, который решает гибкую (flexible) задачу RSA с малой открытой экспонентой может быть преобразован в эффективный алгоритм факторизации модуля N=pq.

Таким образом, задача RSA c малой экспонентой e трудно решаема в классе указанных алгоритмов, при условии, что такой является задача факторизации.

New Attacks on RSA with Small Secret CRT-Exponents

(Новые атаки на схему RSA с малыми секретными CRT-экспонентами)

Daniel Bleichenbacher, Alexander May

Известно, что существует эффективный метод для расшифрования/подписи по схеме RSA, если секретная экспонента d является малой величиной по модулю

(p-1) и (q-1). Такие d называются малыми CRT-экспонентами.

Неизвестно полиномиальных атак на малые CRT-экспоненты, то есть результатов аналогичных атаке Wiener или Boneh-Durfee. На CRYPTO 2002 дано частичное решение задачи, когда простые делители p и q не сбалансированы (A. May), именно при q< N, где N=pq – модуль схемы.

В данной работе улучшена эта оценка для q< N. Это близко к сбалансированной схеме RSA.

Также в работе представлен второй результат при сбалансированных делителях p и q, но в случае, когда экспонента e значительно меньше модуля N. Более точно, установлено существование полиномиальной атаки в случае, когда

d, d < min {(N/e), N}.

Для доказательства используется метод Копперсмита (Coppersmith) нахождения малых корней сравнений.

Метод атаки может быть применен к двум быстрым вариантам схемы RSA, недавно предложенных Galbraith, Heneghan, McKee (ACISP`2005) и Sun, Wu (ePrint Archiv 2005/053).

A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants (Стратегия нахождения корней многочленов от многих переменных и ее новые применения в атаках на варианты схемы RSA)Ellen Jochemsz, Alexander May

В работе описывается стратегия нахождения малых корней многочленов от многих переменных с использованием метода Копперсмита ( Eurocrypt`1996), основанного на алгебраических решетках.

Предложены новые полиномиальные атаки на 2 варианта схемы RSA.

2.7. Цифровая подпись

Одним из основных применений криптосистем с открытым ключом является их использование при создании так называемой цифровой подписи (digital signature). Впервые идея цифровой подписи была высказана все в той же известной работе Диффи и Хеллмана [4].

Для ее изложения потребуем, чтобы преобразования зашифрования и расшифрования из определения криптосистемы с открытым ключом действовали также соответственно на пространствах шифрованных и открытых текстов.

,

и к тому же преобразование было бы обратным преобразованием к , то есть выполнялось бы соотношение

для любого открытого текста .

Теперь, если некий пользователь а желает послать сообщение M пользователю B с подтверждением своего авторства этого сообщения, то он может воспользоваться своим секретным преобразованием = , вычислить величину из и послать это значение (именно оно и будет цифровой подписью) пользователю B. То есть в этом случае преобразование используется как шифрующее преобразование текста M В этом смысле система цифровой подписи обратна системе открытого шифрования.

Пользователь B, а также любой другой пользователь, знающий открытое преобразование пользователя А, может убедиться в авторстве сообщения M вычислением этого сообщения из соотношения и проверкой, является ли полученное значение осмысленным открытым текстом. Здесь преобразование действует как преобразование расшифрования.

Авторство пользователя а основано на том, что только он знает секретное преобразование . Злоумышленник, желающий подменить сообщение M на другое осмысленное сообщение M', должен решить задачу нахождения такого значения C', что

M' =(C')

В силу же односторонней природы преобразования сделать это вычислительно невозможно.

В действительности, для сокращения времени подписывания и размера подписи (а также и для других целей) в процессе подписи используется общеизвестная функция H, действующая на пространстве открытых текстов и отображающая любое сообщение M в сообщения h(m) фиксированного малого размера, которое далее и преобразуется в подпись . Пользователь B, получив сообщение M и подпись к нему , может также вычислить H(M) и проверить выполнимость соотношения

Функция H называется функцией хэширования (hash function). Более подробно она будет рассмотрена отдельно.

Теперь будет понятно следующее определение [54] схемы (системы) цифровой подписи, которая включает следующие компоненты.

1. Пространство открытых сообщений , к которым применяется алгоритм цифровой подписи.

2. Пространство секретных параметров , которые выбираются пользователем.

3. Алгоритм G генерации за полиномиальное время пары - открытого и секретного ключей по выбранному параметру k. (Здесь, как и в ряде учебников, отождествляются открытое и секретные преобразования и с открытым и секретным ключами.)