Атака Винера на RSA при экспоненте равной 3

@Marchcat · Регистрация: 09.01.2015

Author24 — интернет-сервис помощи студентам

Добрый день ! Стало интересно RSA шифрование . У меня есть RSA-Signature (ASN1) . Есть малая експонента для расшифровки равная 3 . Есть Public Modulus 1024 bit. Ну и соответствено расшифрованный ASN1. Хочу вычислить экспоненту для зашифровки.
Точне произвести так называемую Атаку Винера. Если ли у кого реализация . Очень хотелось бы посмотреть .

untyped · 14.10.2019, 18:02

Хабр:

Это все потому, что у кого-то слишком маленькая экспонента: атака Хастада на RSA в задании NeoQUEST-2016

не?

@Marchcat · 14.10.2019, 18:08 **[ТС]**

Читал )) С Питоном мало знаком . Мне бы что - то на С ))

Добавлено через 2 минуты
И как я понял атака Хастада нужна для вычисления ASN1 . При разных ключах и одинаковом ASN1.

@grizlik78 · 15.10.2019, 00:19

Сообщение от Marchcat

С Питоном мало знаком

Так знакомься больше. Для опытов над криптографией язык очень подходящий.
Вот моя реализация атаки Винера:

Python

from fractions import Fraction
 
def private_key_by_wiener(e, N):
    alpha = Fraction(e,  N)
    a = int(alpha)
    q, q1 = 1, 0 
    x = 123456788889 # значение с потолка.
    while alpha - a:
        alpha = 1 / (alpha - a)
        a = int(alpha)
        q, q1 = a*q + q1, q
        if x == pow(pow(x, e, N), q, N):
            return q

Там, по хорошему, надо на нескольких случайных x проверять, вроде. Но и так с взятым наобум значением с большой долей вероятности всё будет нормально.
Fraction — это просто представление дроби в виде отдельных числителя и знаменателя, что бы не иметь дел с погрешностями.
Всё остальное вроде вполне очевидно должно быть как реализуется на си. Только про большие числа надо не забывать и использовать gmp какую-нибудь.

Добавлено через 4 минуты
Только по известной маленькой экспоненте большую неизвестную не найти. Наоборот, должна быть известна большая.

@Marchcat · 15.10.2019, 01:35 **[ТС]**

мне бы узнать d =< N в 0.292 степени )))

Добавлено через 26 минут
допустим как массив байт превратить в большое число я понял

C#

1 2	byte[] byteArray = { 0xEF, 0x11, 0x34, 0x37, 0x96, 0x15, 0x24, 0x73, 0x42, 0x01, 0x00}; BigInteger N = new BigInteger(byteArray);

а вот как возвести в степень 0.292
если только не найти два числа которые дадут в делении 0.292 (a и b) . и не возвести N в степень a и извлечь корень b

@grizlik78 · 15.10.2019, 15:49

Сообщение от Marchcat

мне бы узнать d =< N в 0.292 степени )))

В исходном виде атака Винера работает до N^0.25. Моя реализация для этого варианта.

Сообщение от Marchcat

а вот как возвести в степень 0.292

Приближённо — можно через логарифм и экспоненту.

C#

1	Math.Exp(BigInteger.Log(N) * 0.292)

А ещё лучше отказаться от экспоненты и сравнивать логарифмы, так не будет проблем с возможным переполнением числа double. Но это всё-равно приближённые числа будут сравниваться.
Для более точного сравнения (хотя бы до конца целой части) всё-равно потребуются специализированные библиотеки для вычислений с произвольной точностью.

@Marchcat · 15.10.2019, 16:07 **[ТС]**

Ну 1/4 можно два раза прогнать через квадратный корень и потом разделить на 3 так как экспонента равна 3

@grizlik78 · 15.10.2019, 16:21

Сообщение от Marchcat

Ну 1/4 можно два раза прогнать через квадратный корень

Можно. А можно просто взять и вычислить корень четвёртой степени методом Ньютона до последнего знака целой части.
Но к атаке Винера это не особо относится. Там этого всего не надо, если условия уже выполнены.

Сообщение от Marchcat

потом разделить на 3 так как экспонента равна 3

Что?

Ничего не понял. Зачем делить на экспоненту и почему она равна 3?

Добавлено через 2 минуты
Ах, это та экспонента, которая из исходного вопроса. Экспонента RSA. Ну всё-равно непонятно, зачем на неё делить.

@Marchcat · 15.10.2019, 16:29 **[ТС]**

Ну как же . нам надо вычислить d . e равна 3 или на оборот это не имеет значения . И в статье описано что при экспоненте малой . т.е 3 . d=< (1/3) * на N в степени 1/4

Добавлено через 23 секунды
https://ru.wikipedia.org/wiki/RSA
Обобщенная атака Винера

Добавлено через 5 минут
Точнее предел экспоненты

@grizlik78 · 15.10.2019, 17:01

Боюсь, что если одна экспонента равна 3, то другая никак не может быть меньше N^0.25.

Добавлено через 16 минут
В статье на Википедии не говорится, что e=3. Коэффициент (1/3) никак не связан с открытой экспонентой. Для того, чтобы секретная экспонента удовлетворяла указанному неравенству открытая экспонента должна быть значительно больше секретной, иначе быть не может чисто математически, ибо e*d > (p-1)*(q-1) и сравнимо по порядку с числом N. Значит если один сомножитель относительно маленький, то другой обязан быть большим.

Добавлено через 1 минуту
если d < N^0.25, то e > N^0.75.

Добавлено через 4 минуты
В openssl в качестве открытой экспоненты всегда используется 65537, в некоторых других реальных реализациях вполне может использоваться число 3, никакой угрозы само по себе это не несёт, и даже напротив, гарантирует что секретная экспонента будет большой и атака Винера не приведёт к успеху. Возможно тройка даст возможность использовать какие-то другие атаки, но это нужно рассматривать уже отдельно.

@Marchcat · 15.10.2019, 17:27 **[ТС]**

Как раз на просторах интернета и говориться что для расшифровки используется малая экспонента . Это и есть осн уязвимость. А такую экспоненту берут что бы в микрочипах была быстрая расшифровка

Добавлено через 1 минуту
Что то не получается у меня расшифровать так ((

C#

            BigInteger N = new BigInteger(byteArrayN);
            BigInteger C = new BigInteger(byteArrayC);
            BigInteger M = BigInteger.ModPow(C, 3, N);
 
           // log.AppendText(N.ToString("X2") + "\n" + "\n");
           // log.AppendText(C.ToString("X2") + "\n" + "\n");
            log.AppendText(M.ToString("X2") + "\n" + "\n");

N - модуль
3 - экпонента
С - зашифрованная часть ((

Добавлено через 15 минут
И так то же что-то не хотит

C#

            BigInteger N = new BigInteger(byteArray);
            BigInteger C = new BigInteger(byteArray2);
            BigInteger A = BigInteger.Pow(C, 3);
            BigInteger M ;
            BigInteger A1 = BigInteger.DivRem(A, N, out M);

@grizlik78 · 15.10.2019, 17:29

Если 3 это секретная экспонента (мы ведь о шифровании, а не о подписи?) то первый код правильный и либо исходные данные неверны, либо неправильно интерпретируются расшифрованные данные.

@Marchcat · 15.10.2019, 17:34 **[ТС]**

нет как раз о подписи ASN1.

Добавлено через 2 минуты
Может я что-то не доглядел . Но я думал что подпись накрывается RSA и все ))

Добавлено через 1 минуту
В первом коде ModPow возводит в степень и делитель ( modulo )

@Marchcat · 15.10.2019, 17:48 **[ТС]**

Вот что у меня получилось в он-лайн декрипторе

@grizlik78 · 15.10.2019, 17:50

выглядит как правильно расшифрованный текст.

@Marchcat · 15.10.2019, 17:56 **[ТС]**

так оно и есть . А у себя я не могу это реализовать в обход стандартной rsa библиотеки ((

Добавлено через 4 минуты
вот код кнопки

C#

        private void button1_Click(object sender, EventArgs e)
        {
            string modulo = t_modulo.Text;
            modulo = modulo.Replace(" ", "");
            int NumberChars = modulo.Length;
            byte[] byteArray = new byte[NumberChars / 2];
            for (int i = 0; i < NumberChars; i += 2)
                byteArray[i / 2] = Convert.ToByte(modulo.Substring(i, 2), 16);
 
            byte[]byteArrayN = new byte[byteArray.Length];
            for (int k = 0; k < byteArray.Length; k++)
            {
                byteArrayN[k] = byteArray[byteArray.Length - 1 - k];
            }
 
 
            string crypt = t_crypt.Text;
            crypt = crypt.Replace(" ", "");
            int NumberChars2 = crypt.Length;
            byte[] byteArray2 = new byte[NumberChars2 / 2];
            for (int i = 0; i < NumberChars2; i += 2)
                byteArray2[i / 2] = Convert.ToByte(crypt.Substring(i, 2), 16);
 
            byte[] byteArrayC = new byte[byteArray2.Length];
            for (int k = 0; k < byteArray2.Length; k++)
            {
                byteArrayC[k] = byteArray2[byteArray2.Length - 1 - k];
            }
 
 
            BigInteger N = new BigInteger(byteArrayN);
            BigInteger C = new BigInteger(byteArrayC);
            BigInteger A = BigInteger.Pow(C, 3);
            BigInteger M ;
            BigInteger A1 = BigInteger.DivRem(A, N, out M);
 
            log.AppendText(N.ToString("X2") + "\n" + "\n");
            log.AppendText(C.ToString("X2") + "\n" + "\n");
            log.AppendText(M.ToString("X2") + "\n" + "\n");
            log.AppendText(A.ToString("X2") + "\n" + "\n");
 
        }

@grizlik78 · 15.10.2019, 18:12

Возможно нужно использовать обратный порядок при чтении N. Без конкретных чисел можно только гадать.
Найти секретный ключ наверняка всё-равно не удастся. Открытый равен 3, значит секретный большой и атака Винера сразу отпадает.

Добавлено через 9 минут

Сообщение от grizlik78

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

Вон, в строках 13 и 27 реализован разворот массивов для N и C. В твоём коде (или исходных данных) это есть? Преобразование из big endian в little endian.
Больше мне тут гадать не о чем. Код RSA через PowMod выглядит правильно.

Добавлено через 1 минуту
Стоп. Или это и есть твой код?

Добавлено через 2 минуты
Я C# не использую, без исходных данных (N и C) ничего не могу сделать.

@Marchcat · 15.10.2019, 19:11 **[ТС]**

Попробовал

C#

1 2	BigInteger N = new BigInteger(byteArrayN); BigInteger C = new BigInteger(byteArrayC);

C#

1 2	BigInteger N = new BigInteger(byteArray); BigInteger C = new BigInteger(byteArray2);

C#

1 2	BigInteger N = new BigInteger(byteArrayN); BigInteger C = new BigInteger(byteArray2);

C#

1 2	BigInteger N = new BigInteger(byteArray); BigInteger C = new BigInteger(byteArrayC);

что - то не совпало (( и оставил

C#

1	BigInteger M = BigInteger.ModPow(C, 3, N);

Добавлено через 3 минуты
В личку отправил данные ))

Добавлено через 52 минуты
Урррра ! Спасибо огромное ))

@Marchcat 2 / 2 / 1 Регистрация: 09.01.2015 Сообщений: 382
		1
	Атака Винера на RSA при экспоненте равной 3 14.10.2019, 17:46. Показов 5781. Ответов 17 Метки атака винера (Все метки) Добрый день ! Стало интересно RSA шифрование . У меня есть RSA-Signature (ASN1) . Есть малая експонента для расшифровки равная 3 . Есть Public Modulus 1024 bit. Ну и соответствено расшифрованный ASN1. Хочу вычислить экспоненту для зашифровки. Точне произвести так называемую Атаку Винера. Если ли у кого реализация . Очень хотелось бы посмотреть . 0

untyped 531 / 180 / 39 Регистрация: 18.08.2012 Сообщений: 907
	14.10.2019, 18:02	2
	Хабр: Это все потому, что у кого-то слишком маленькая экспонента: атака Хастада на RSA в задании NeoQUEST-2016 не? 0

@Marchcat 2 / 2 / 1 Регистрация: 09.01.2015 Сообщений: 382
	14.10.2019, 18:08 [ТС]	3
	Читал )) С Питоном мало знаком . Мне бы что - то на С )) Добавлено через 2 минуты И как я понял атака Хастада нужна для вычисления ASN1 . При разных ключах и одинаковом ASN1. 0

@Marchcat 2 / 2 / 1 Регистрация: 09.01.2015 Сообщений: 382
	15.10.2019, 16:07 [ТС]	7
	Ну 1/4 можно два раза прогнать через квадратный корень и потом разделить на 3 так как экспонента равна 3 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	15.10.2019, 16:21	8
	Сообщение от Marchcat Ну 1/4 можно два раза прогнать через квадратный корень Можно. А можно просто взять и вычислить корень четвёртой степени методом Ньютона до последнего знака целой части. Но к атаке Винера это не особо относится. Там этого всего не надо, если условия уже выполнены. Сообщение от Marchcat потом разделить на 3 так как экспонента равна 3 Что? Ничего не понял. Зачем делить на экспоненту и почему она равна 3? Добавлено через 2 минуты Ах, это та экспонента, которая из исходного вопроса. Экспонента RSA. Ну всё-равно непонятно, зачем на неё делить. 0

@Marchcat 2 / 2 / 1 Регистрация: 09.01.2015 Сообщений: 382
	15.10.2019, 16:29 [ТС]	9
	Ну как же . нам надо вычислить d . e равна 3 или на оборот это не имеет значения . И в статье описано что при экспоненте малой . т.е 3 . d=< (1/3) * на N в степени 1/4 Добавлено через 23 секунды https://ru.wikipedia.org/wiki/RSA Обобщенная атака Винера Добавлено через 5 минут Точнее предел экспоненты 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	15.10.2019, 17:01	10
	Боюсь, что если одна экспонента равна 3, то другая никак не может быть меньше N^0.25. Добавлено через 16 минут В статье на Википедии не говорится, что e=3. Коэффициент (1/3) никак не связан с открытой экспонентой. Для того, чтобы секретная экспонента удовлетворяла указанному неравенству открытая экспонента должна быть значительно больше секретной, иначе быть не может чисто математически, ибо ed > (p-1)(q-1) и сравнимо по порядку с числом N. Значит если один сомножитель относительно маленький, то другой обязан быть большим. Добавлено через 1 минуту если d < N^0.25, то e > N^0.75. Добавлено через 4 минуты В openssl в качестве открытой экспоненты всегда используется 65537, в некоторых других реальных реализациях вполне может использоваться число 3, никакой угрозы само по себе это не несёт, и даже напротив, гарантирует что секретная экспонента будет большой и атака Винера не приведёт к успеху. Возможно тройка даст возможность использовать какие-то другие атаки, но это нужно рассматривать уже отдельно. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	15.10.2019, 17:29	12
	Если 3 это секретная экспонента (мы ведь о шифровании, а не о подписи?) то первый код правильный и либо исходные данные неверны, либо неправильно интерпретируются расшифрованные данные. 0

@Marchcat 2 / 2 / 1 Регистрация: 09.01.2015 Сообщений: 382
	15.10.2019, 17:34 [ТС]	13
	нет как раз о подписи ASN1. Добавлено через 2 минуты Может я что-то не доглядел . Но я думал что подпись накрывается RSA и все )) Добавлено через 1 минуту В первом коде ModPow возводит в степень и делитель ( modulo ) 0

@Marchcat 2 / 2 / 1 Регистрация: 09.01.2015 Сообщений: 382
	15.10.2019, 17:48 [ТС]	14
	Вот что у меня получилось в он-лайн декрипторе Миниатюры 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	15.10.2019, 17:50	15
	выглядит как правильно расшифрованный текст. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	15.10.2019, 18:12	17
	Сообщение было отмечено Marchcat как решение Решение Возможно нужно использовать обратный порядок при чтении N. Без конкретных чисел можно только гадать. Найти секретный ключ наверняка всё-равно не удастся. Открытый равен 3, значит секретный большой и атака Винера сразу отпадает. Добавлено через 9 минут Сообщение от grizlik78 Возможно нужно использовать обратный порядок при чтении N. Вон, в строках 13 и 27 реализован разворот массивов для N и C. В твоём коде (или исходных данных) это есть? Преобразование из big endian в little endian. Больше мне тут гадать не о чем. Код RSA через PowMod выглядит правильно. Добавлено через 1 минуту Стоп. Или это и есть твой код? Добавлено через 2 минуты Я C# не использую, без исходных данных (N и C) ничего не могу сделать. 1

Атака Винера на RSA при экспоненте равной 3

Решение