I need help. RSA in java, Собственная реализация RSA. Проблема кодирования.

[igorka]

   BigInteger encrypt(byte [] message) throws Exception {
        byte[] block = new byte[2];
        ByteArrayOutputStream mes = new ByteArrayOutputStream();
        for(int i = 0; i < message.length; i+=2){
            System.arraycopy(message, i, block, 0, 2);
            byte [] tmp = new BigInteger(block).modPow(publicKey, modulus).toByteArray();
            if(tmp.length % 8 != 0)  {
              System.out.println("Dow! length = " + tmp.length);
            }
            mes.write(tmp);  
        }      
        return new BigInteger(mes.toByteArray());
    }

Это дебаг версия функции кодирования. В качестве параметров функция принимает исходное сообщение(условно четной длинны).
Потом сообщение разбивается на блоки по два байта, и шифруется алгоритмом RSA. Длинна ключа(модуля) 64 бит, 8 байт.

Проблема заключается в том что раз от разу [B]гуляет длина закодированого блока!,
для проверки добавлено условие if(tmp.length % 8 != 0)

Подозреваю что собака зарыта где-то в классе BigInteger. modPow() должна возвращать всегда числа одинаковой разрядности? или нет?
Что делать? Хелп ми плз.

[wind]

Размер массива байт, который возвращает BigInteger.toByteArray(), зависит от разрядности числа.

[igorka]

wind
Вот именно. Но разве разрядность не должна сохранятся? Тоесть при всех вызовах modPow() разрядность должна оставатся одна и таже и зависеть от modulus.
?!?

[wind]

Цитата igorka @ 22.12.07, 23:21

Тоесть при всех вызовах modPow() разрядность должна оставатся одна и таже и зависеть от modulus.

Нет. При неизменном modulus число разрядов результата зависит от исходного числа. Вы уверены в содержимом message и modulus?

Сообщение отредактировано: wind - 22.12.07, 23:39

[igorka]

import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.ByteArrayOutputStream;
 
public class RSA {
   private final static BigInteger one      = new BigInteger("1");
   private final static SecureRandom random = new SecureRandom();
 
   private BigInteger privateKey;
   private BigInteger publicKey;
   private BigInteger modulus;
   private final static int N = 64;
 
   // generate an N-bit (roughly) public and private key
   RSA() {
      BigInteger p;
      BigInteger q;
      BigInteger e;
      BigInteger d;
      do{
      p = BigInteger.probablePrime(N/2, random);
      System.out.println("p = " + p);
      q = BigInteger.probablePrime(N/2, random);
      System.out.println("q = " + q);
      }
      while(p == q);
      BigInteger phi = (p.subtract(one)).multiply(q.subtract(one));
      System.out.println("phi = " + phi);
      modulus    = p.multiply(q);                                  
      System.out.println("mod = " + modulus);
      //publicKey  = new BigInteger("65537");     // common value in practice = 2^16 + 1
      //privateKey = publicKey.modInverse(phi);
      e = new BigInteger("3");
       while(phi.gcd(e).intValue() > 1) e = e.add(new BigInteger("2"));
      d = e.modInverse(phi);
      System.out.println("e = " + e);
      System.out.println("d = " + d);
      publicKey = e;
      privateKey = d;
   }
 
 
   BigInteger encrypt(byte [] message) throws Exception {
        byte[] block = new byte[2];
        ByteArrayOutputStream mes = new ByteArrayOutputStream();
        for(int i = 0; i < message.length; i+=2){
            System.arraycopy(message, i, block, 0, 2);
            byte [] tmp = new BigInteger(block).modPow(publicKey, modulus).toByteArray();
            if(tmp.length % 8 != 0)  {
              System.out.println("Dow! length = " + tmp.length);
            }
            mes.write(tmp);  
        }      
        return new BigInteger(mes.toByteArray());
    }
 
 
   BigInteger decrypt(byte [] encrypted) throws Exception {
   System.out.println("N length   = " + modulus.bitLength()/8);
   System.out.println("encrypted len   = " + encrypted.length);
        byte[] block = new byte[modulus.bitLength()/8];
        ByteArrayOutputStream mes = new ByteArrayOutputStream();
        for(int i = 0; i < encrypted.length; i+=modulus.bitLength()/8){
            System.arraycopy(encrypted, i, block, 0, modulus.bitLength()/8);
            mes.write(new BigInteger(block).modPow(privateKey, modulus).toByteArray());  
        }      
      return new BigInteger(mes.toByteArray());
   }
 
   public String toString() {
      String s = "";
      s += "public  = " + publicKey  + "\n";
      s += "private = " + privateKey + "\n";
      s += "modulus = " + modulus;
      return s;
   }
 
   public static void main(String[] args) {
      //int N = Integer.parseInt(args[0]);
      RSA key = new RSA();
    
      // create random message, encrypt and decrypt
      //BigInteger message = new BigInteger(N-1, random);
 
      //// create message by converting string to integer
      // String s = "test";
      byte[] bytes = args[0].getBytes();
      BigInteger message = new BigInteger(bytes);
      try{
      System.out.println("message   = " + message);
      BigInteger encrypt = key.encrypt(message.toByteArray());
      System.out.println("encrpyted = " + encrypt);
      BigInteger decrypt = key.decrypt(encrypt.toByteArray());
      System.out.println("decrypted = " + decrypt);
    }
      catch(Exception e) {
        System.out.println("Exception" );
        e.printStackTrace();
      };
   }
}

Сделаем вот так. В качестве параметра передаем четное кол-во символов.
Кодирует нормально, а вот декодирует не всегда. я уже ничего не могу понять,
может проблема где-то рядом, но что-то никак не могу разобратся. Повториете запуск
програмы с одними и теми же параметрами несколько раз.


Вот что получается у меня... где трабля вылазит?
Прикреплённый файлtest.txt.gz (0.96 Кбайт, скачиваний: 392)

[igorka]

Спасибо, что помогли, ну или попытались. Вот что у меня получилось, может кто будет страдать подобным и ему пригодится.
Канешна недостатков много, еще дорабатывать и дорабатывать, поэтому выслушаю все рекомендации.
Тестировал ключи вплоть до 8192 - полет нормальный.

Еще интересует вопрос по быстродействию, оптимальней будет брать блоки по два байта(или по одному?) как делал я, или
брать блоки размером (РАЗМЕР_КЛЮЧА - 1), что будет быстрее?

import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.ByteArrayOutputStream;
 
public class RSA {
   private final static BigInteger one      = new BigInteger("1");
   private final static SecureRandom random = new SecureRandom();
 
   private BigInteger privateKey;
   private BigInteger publicKey;
   private BigInteger modulus;
   private final static int N = 64;
 
   // generate an N-bit (roughly) public and private key
   RSA() {
      BigInteger p;
      BigInteger q;
      BigInteger e;
      BigInteger d;
      do{
      p = BigInteger.probablePrime(N/2, random);
      System.out.println("p = " + p);
      q = BigInteger.probablePrime(N/2, random);
      System.out.println("q = " + q);
      }
      while(p == q);
      BigInteger phi = (p.subtract(one)).multiply(q.subtract(one));
      System.out.println("phi = " + phi);
      modulus    = p.multiply(q);                                  
      System.out.println("mod = " + modulus);
      e = new BigInteger("3");
       while(phi.gcd(e).intValue() > 1) e = e.add(new BigInteger("2"));
      d = e.modInverse(phi);
      System.out.println("e = " + e);
      System.out.println("d = " + d);
      publicKey = e;
      privateKey = d;
   }
 
 
   String encrypt(byte [] message) throws Exception {
        int blockSize = 2;
        byte[] block = new byte[blockSize];
        System.out.println("message length  = " + message.length );
        StringBuffer sb = new StringBuffer();
        ByteArrayOutputStream mes = new ByteArrayOutputStream();
        for(int i = 0; i < message.length; i+=blockSize){
            if(message.length == (i+1)){
              blockSize--;
              block = new byte[blockSize];
              System.out.println("block decrement!");
            }
            System.arraycopy(message, i, block, 0, blockSize);
            byte [] tmp = new BigInteger(block).modPow(publicKey, modulus).toByteArray();
            mes.write(tmp);
            sb.append(new BigInteger(tmp).toString(16)).append("\n");  
        }
        return sb.toString();      
    }
 
 
   String decrypt(String encrypted) throws Exception {
   System.out.println("N length   = " + modulus.bitLength()/8);
   System.out.println("encrypted len   = " + encrypted.length());
        BigInteger block;
   ByteArrayOutputStream mes = new ByteArrayOutputStream();
        int i = 0;
        int j = 0;
        while(i < (encrypted.length()-1)){
         i++;
         if(encrypted.charAt(i) == '\n'){
          block = new BigInteger(encrypted.substring(j, i), 16);
          mes.write(block.modPow(privateKey, modulus).toByteArray());
      System.out.println("block = " + encrypted.substring(j, i) + "end" );
          j = i+1;
         }
          
        }
              
       return mes.toString();
   }
 
   public String toString() {
      String s = "";
      s += "public  = " + publicKey  + "\n";
      s += "private = " + privateKey + "\n";
      s += "modulus = " + modulus;
      return s;
   }
 
   public static void main(String[] args) {
      RSA key = new RSA();
    
      byte[] bytes = args[0].getBytes();
      BigInteger message = new BigInteger(bytes);
      try{
      System.out.println("message   = " + message);
      String encrypt = key.encrypt(bytes);
      System.out.println("encrpyted = " + encrypt);
      String decrypt = key.decrypt(encrypt);
      System.out.println("decrypted = " + decrypt);
    }
      catch(Exception e) {
        System.out.println("Exception" );
        e.printStackTrace();
      };
   }
}

[wind]

Цитата igorka @ 23.12.07, 23:57

Спасибо, что помогли, ну или попытались.

Честно делали вид А что, собственно, было не так, вкратце?

Цитата igorka @ 23.12.07, 23:57

Еще интересует вопрос по быстродействию, оптимальней будет брать блоки по два байта(или по одному?) как делал я, или
брать блоки размером (РАЗМЕР_КЛЮЧА - 1), что будет быстрее?

Поверхностно - больший размер блока -> более быстрая обработка. Но на самом деле всё зависит от реализации арифметики в BigInteger, нужно тестировать.

Сообщение отредактировано: wind - 24.12.07, 00:14

[igorka]

Хм, нашелся баг: если в тестовое приложение в качестве параметра указать русские буквы - то неправильно расшифровует.
ниче нипанимаю
основное приложение так же шифрует и расшифровывает только файлы содержащие латиницу, а хочется не зависить от содержания файла.
Хелп ми а5!

[wind]

Вообще-то, приватный ключ используется для шифрования, а публичный - для расшифровки, а не наоборот. Ещё меня сильно смущают ваши преобразования строк в числа. Вот так всё замечательно работает:

String encryptString(String string) {
        StringBuilder encryptedStringBuilder = new StringBuilder();
        
        for (int i = 0, count = string.length(); i < count; i++) {
            BigInteger digit = BigInteger.valueOf(
                string.charAt(i)
            );
            
            encryptedStringBuilder.append(
                digit.modPow(privateKey, modulus).toString(RADIX)
            );
            encryptedStringBuilder.append(",");
        }
        
        return encryptedStringBuilder.toString();
    }
    
    String decryptString(String string) {
        StringBuilder decryptedStringBuilder = new StringBuilder();
        
        for (String block : string.split(",")) {
            decryptedStringBuilder.append(
                (char) new BigInteger(block, RADIX).modPow(publicKey, modulus).intValue()
            );
        }
        
        return decryptedStringBuilder.toString();
    }

[igorka]

[wind

Шифруем публичным, расшифровываем приватным! Это основа ассимитричных методов шифрования.
У отправителя находится только ОТКРЫТЫЙ ключ, он им шифрует сообщение и передает получателю.
Получатель расшифровывает сообщения использую ЗАКРЫТЫЙ ключ. Предварительно получатель генерирует
пару ключей и передает открытый ключ отправителю. Такая схема не нуждается в защищенном канале
для передачи ЗАКРЫТОГО ключа

Добавлено 25.12.07, 22:38
А если надо иметь на входе в encrypt и на выходе с decrypt массив байт, а не строку? Строка используется лишь для хранения зашифрованых файлов.

Сообщение отредактировано: igorka - 25.12.07, 22:38

[wind]

Цитата igorka @ 25.12.07, 22:23

У отправителя находится только ОТКРЫТЫЙ ключ, он им шифрует сообщение и передает получателю.
Получатель расшифровывает сообщения использую ЗАКРЫТЫЙ ключ.

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

Цитата igorka @ 25.12.07, 22:23

А если надо иметь на входе в encrypt и на выходе с decrypt массив байт, а не строку? Строка используется лишь для хранения зашифрованых файлов.

Что-то подсказывает мне, что такому развитию событий ничто не мешает Просто вы теряете целостность данных где-то по дороге, преобразовывая строку в числа методами, для этого не особо предназначенными

[batigoal]

Цитата igorka @ 25.12.07, 22:23

У отправителя находится только ОТКРЫТЫЙ ключ

в чем же тогда его "открытость"? Он потому и открытый, что публикуется для получателей. А "закрытый" - потому что он доступен только отправителю.

[igorka]

wind
batigoal
http://ru.wikipedia.org/wiki/RSA
Советую почитать, и не говорить глупостей.

Сообщение отредактировано: igorka - 26.12.07, 18:49

[wind]

Цитата igorka @ 26.12.07, 18:47

Советую почитать, и не говорить глупостей.

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

[batigoal]

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

[igorka]

wind
batigoal
Сейчас немного нехватает времени, чтобы обьяснить схему ассимитричных алгоритмов.
Если поможете мне с моей проблемкой, и я немного освобожусь, то освежу ваши
знания по защите информации. Все правильно учили, терминология была таже что и сейчас,
просто вы немного запутались.

[wind]

Цитата igorka @ 26.12.07, 19:22

Если поможете мне с моей проблемкой, и я немного освобожусь, то освежу ваши
знания по защите информации. Все правильно учили, терминология была таже что и сейчас,
просто вы немного запутались.

Освежите, если вас не затруднит. Также особенно - какой смысл вообще во всём этом предприятии, если закрытый ключ прилагается к сообщению.

[igorka]

В данном случае RSA используется не для цифровой подписи, а для шифрования. (У RSA как минимум два назначения, исторически первое из них - шифрование).
Самым большим недостатком симметричных систем шифрования была необходимость закрытого канала для передачи СЕКРЕТНОГО ключа.
Ассиметричные системы избавлены от этого недостатка:

-На сторона ПОЛУЧАТЕЛЯ генерируется пара ключей.
-ЗАКРЫТЫЙ ключ используется для расшифрования и никогда никуда не передается, все остается на стороне ПОЛУЧАТЕЛЯ
-ОТКРЫТЫЙ ключе используется для шифрования сообщений, и открыто публикуется
-ОТПРАВИТЕЛЬ имея только ОТКРЫТЫЙ ключ шифрует сообщение и отправляет ПОЛУЧАТЕЛЮ
-сообщение можно расшифровать ТОЛЬКО ЗАКРЫТЫМ ключом, поэтому никто кроме ПОЛУЧАТЕЛЯ на может его расшифровать
(помниет, ЗАКРЫТЫЙ ключ остался у ПОЛУЧАТЕЛЯ и никуда не передавался)
-ПОЛУЧАТЕЛЬ расшифровывает сообщение имея свой уникальный ЗАКРЫТЫЙ ключ
Вскрыть сообщение по ходу передачи невозможно, канал для передачи ЗАКРЫТОГО ключа не трубуется. Волки целы, овцы сыты.

Ассиметричные методы имеют свои недостатки, это оочень маленькая скорость шифрования и оочень большой размеш зашифрованых сообщений.
Поэтому используются так званые комбинированые системы шифрования: сообщение шифруется симетричным методом (DES, ГОСТ, и т.д.) а ключ
шифруется ассиметричным методом, тем же RSA.

Я пишу программулину для шифрования сообщения алгоритмом RSA.

Второе применение RSA - это цифровая подпись. Основано на ХЭШ функция и взаимозаменяемости ключей в RSA.
-ОТПРАВИТЕЛЬ берет ХЭШ сообщения и фишрует его RSA используя ОТКРЫТЫЙ ключ(можно использовать и ЗАКРЫТЫЙ, они полностью взаимозаменяемы)
-ОТПРАВИТЕЛЬ отправляет сообщение с прекрепленной подписью [ЗАШИФРОВАНЫЙ ХЭШ + ЗАКРЫТЫЙ КЛЮЧ]
-ПОЛУЧАТЕЛЬ расшифровывает ЗАШИФРОВАНЫЙ ХЭШ с помощью ЗАКРЫТОГО КЛЮЧА, получает ХЭШ переданного сообщения, сравнивает расшифрованый и полученый ХЭШи,
если они совпали - подпись верна, не совпали - не верна.

Вот вроде, все.

Я уже почти закончил свою программулину, но вот не могу одалеть этот баг. Если интересно, могу выложить исходный код класса и ГУИ, допишем вместе.
Там еще нужны доработки интерфейса и немного оптимизации, о оптимизировал шифрование, очень сильно затормозив расшифрование:(, ну и конешно баг пофиксить:)
Прога работает с ключами до 8096 - теоретически можно и больше, но кому это надо?

[wind]

Цитата igorka @ 26.12.07, 20:55

Ассиметричные методы имеют свои недостатки, это оочень маленькая скорость шифрования и оочень большой размеш зашифрованых сообщений.

Есть ещё один недостаток - криптостойкость тем ниже, чем больше блоков, размер которых сравним с размером ключа в сообщении. Это вторая причина, по которым использовать RSA для шифрования данных не рекомендуют.

По примерам.

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

Наверняка вы не так давно получили свои представления из какого-то источника (ведь явно какую-то учебную задачу выполняете). Не могли бы вы дать хоть какую-либо информацию о нём?

[nauris.nikos]

wind У меня твой пример кода не расшифровывает сообщение.
бяка какая то получается.
в чем трабла?
очень надо.

[Большой Синий Кит]

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

[dark_barker]

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