Почему большие ключи RSA не шифруют до уникального значения? - PullRequest
Новая
       57

Почему большие ключи RSA не шифруют до уникального значения?

2 голосов
/ 16 января 2020

Я вычисляю два 2048-битных простых числа, используя метод BigInteger probablePrime, следующим образом: BigInteger.probablePrime(2048, new Random());. Соответственно, давайте назовем эти простые числа p и q. Я вычисляю частную экспоненту, используя следующий код: BigInteger.TWO.multiply(r).add(BigInteger.ONE).divide(e);, где e эквивалентно BigInteger.valueOf(3), а r эквивалентно BigInteger со значением: (p - 1)(q - 1).

Создание зашифрованный BigInteger выглядит следующим образом: message.modPow(e, r), где message - это BigInteger.

Допустим, я зашифрую sh для шифрования 774356626352684872522728355634287624183747537718011900969524254770659766752605764866132228010801740792162094. Это большое целое число «Быстрая коричневая лиса перепрыгнула через ленивую собаку». преобразуется в двоичный файл, а затем преобразуется в десятичный. Мой результат - 464326058229369014486528960945777245568243099145851675968955902027904135435059026247893552949145149936678174588724345105141605583511438062567406913039976998983678282605288609470234530610515268764924240227134432014767865301287496131771559993377618477929696113174968779730288058725125905006272019930686696412137679303439126584.

Независимо от того, сколько раз я запускаю приведенный выше код, он всегда зашифровывает одно и то же точное значение. Кажется, не имеет значения, какие простые числа он генерирует - зашифрованное значение всегда является выше для этого конкретного значения message.

Теперь вот где это становится особенно своеобразным, если я генерирую 512-битные простые числа, результат уникален Каждый раз, когда я запускаю приведенный выше код, генерируя 512-разрядные простые числа вместо 2048 или даже 1024-разрядных простых, он генерирует уникальный результат при каждом запуске. Однако, если я буду sh генерировать 1024 или 2048-битные простые числа, результат всегда будет одинаковым, независимо от генерируемых простых чисел.

Может кто-нибудь объяснить, почему это происходит, или какие изменения потребуются сделать для кода генерировать уникальные зашифрованные целые числа с использованием 2048-битных простых чисел? В частности, почему он работает для 512 или простых битов, но не для 1024 или простых битов? Я прошу прощения, если это был не самый хорошо продуманный вопрос, поэтому, пожалуйста, не стесняйтесь спрашивать разъяснения, если что-то не так. : 

import java.io.IOException;
import java.math.BigInteger;
import java.security.SecureRandom;

public class Yeet {
    public static void main(String[] args) throws IOException {
        int t = (int) (System.currentTimeMillis() / 1000);

        byte[] date = new byte[]{
          (byte) (t >> 24),
          (byte) (t >> 16),
          (byte) (t >> 8),
          (byte) t,
        };  

        BigInteger p = BigInteger.probablePrime(2048, new SecureRandom(date));
        BigInteger q = BigInteger.probablePrime(2048, new SecureRandom(date));
        BigInteger e = BigInteger.valueOf(3);
        BigInteger r = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

        BigInteger message = new BigInteger("774356626352684872522728355634287624183747537718011900969524254770659766752605764866132228010801740792162094");

        System.out.println(message.modPow(e, r));
    }
}

Запустите его столько раз, сколько захотите. Всегда выдает 464326058229369014486528960945777245568243099145851675968955902027904135435059026247893552949145149936678174588724345105141605583511438062567406913039976998983678282605288609470234530610515268764924240227134432014767865301287496131771559993377618477929696113174968779730288058725125905006272019930686696412137679303439126584. Теперь, если мы поменяем 2048 на 512 в строках 16 и 17, каждый прогон выдаст уникальное значение ...

1 Ответ

4 голосов
/ 16 января 2020

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

Теперь показатель publi c в вашем случае очень мал: 3. Таким образом, вполне вероятно, что небольшой исходный открытый текст меньше после возведения в степень, чем модуль. The quick brown fox jumped over the lazy dog. - 45 символов / байт или 360 бит. Если у вас 360-битное число и вы возводите возведение в степень с 3, тогда вы получите значение 360 x 3 = 1080 бит, что намного ниже модуля 2 x 2048 = 4096 бит, поэтому модульное сокращение не будет выполнено. 2 x 512 = 1024, так что с таким размером простых чисел ваше значение всего на несколько бит больше, чем модуль, поэтому значение модуля имеет значение.

Конечно, вы можете использовать пятое простое число Ферма (F4 ) со значением 65537 вместо. Это приведет к модульному уменьшению до 360 x 65537> 4096. Однако, чтобы быть в безопасности, вы должны использовать метод заполнения, такой как указанный в PKCS # 1 v2.2 . Это расширит значение открытого текста, поэтому представление чисел, зависящее от открытого текста, будет намного ближе к модулю в битах. Результат модульного возведения в степень тогда фактически выполнит по крайней мере несколько уменьшений модуля, и поэтому зависит от различных значений модуля.

Что еще более важно, заполнение PKCS # 1 v1.5 или OAEP, указанное в PKCS # 1 v2.2 сама является случайной, поэтому шифрование одного и того же открытого текста приведет к другому зашифрованному тексту , даже если используется та же пара ключей / модуль . Для ключей больших размеров даже показатель 3 считается безопасным, хотя F4 все еще предпочитается большинством реализаций RSA (OpenSSL, Java, C # /. NET et c. Et c.).

...