# RSA Verschlüsselung



## MeinerEiner (23. Mai 2005)

Hallöle,
versuche mich gerade an einer RSA Verschlüsselung in Java..
Problem dabei ist, wenn ich eine Nachricht verschlüssele und sie dann entschlüssele, ist sie auf einmal doppelt vorhanden.. Sieht so aus, als ob ich die originalnachricht wohl irgendwie mit sich selbst konkateniert habe, und dann verschlüsselt.. aber ich find einfach keinen fehler.....

Zur verdeutlichung mal der quelltext :
Habe erstmal ein Schlüsselpaar erstellt..


```
import java.nio.*;
import java.nio.charset.*;
import java.security.*;
import java.util.Vector;

import javax.crypto.*;


public class Security {
	private KeyPair keyPair;
	private Cipher cipher;
	Charset charset;
	private final int RSABlockSize = 245;
	
	public Security(){
		String nachricht = " die nachricht zum verschlüsseln";
		ByteBuffer buffer = ByteBuffer.allocate(50);
		ByteBuffer decrypt;
		charset = Charset.forName( "ISO-8859-1" );
		buffer.put(charset.encode(nachricht));
		
		generateRSA();
		
		decrypt = encodeWithRSA(buffer,keyPair.getPublic(),RSABlockSize);
		buffer = decodeWithRSA(decrypt,keyPair.getPrivate(),RSABlockSize);
		System.out.println(charset.decode(decrypt));
		System.out.println(charset.decode(buffer));
		
	}
	
	
	
	boolean generateRSA(){
		try {
			KeyPairGenerator kpg = KeyPairGenerator.getInstance( "RSA" );
			kpg.initialize(2048);
			keyPair = kpg.genKeyPair();
			//System.out.println(keyPair.getPrivate());
			//System.out.println(keyPair.getPublic());
			return true;
		} catch (NoSuchAlgorithmException e) {return false;}
		
	}

	public static void main(String[] args) {
		Security sec = new Security();
		
	}
}
```


Als nächstes wird die Nachricht verschlüsselt.... Da bei RSA die blocklänge 245 byte betragen muss, wird die Nachricht auf verschiedene Bytearrays aufgeteilt in einen Vektor verpackt, und dann einzelen verschlüsselt :

```
//Hauptmethode zum Verschlüsseln

ByteBuffer encodeWithRSA(ByteBuffer bufferText, PublicKey pk,int blockSize){
		int allocate=0;
		byte[] byteArray = bufferText.array();
		byteArray = bufferText.array();
		Vector ByteArrays = returnByteArrays(byteArray,blockSize);
		Vector tmpArrays = new Vector();
		try {
		int temp = ByteArrays.size();
		for(int i=0; i < ByteArrays.size(); i++){
			cipher = Cipher.getInstance("RSA");
			cipher.init(Cipher.ENCRYPT_MODE, pk);
			byte[] tmp = cipher.doFinal((byte[])(ByteArrays.get(i)));
			allocate += tmp.length;
			tmpArrays.add(tmp);
		}
			ByteBuffer outputText = ByteBuffer.allocate(allocate);
			for(int i =0; i< tmpArrays.size();i++){
				outputText.put((byte[])(tmpArrays.get(i)));
			}
			outputText.flip();
			return outputText;
			} catch (NoSuchAlgorithmException e) {
				e.printStackTrace();
			} catch (NoSuchPaddingException e) {
				e.printStackTrace();
			} catch (InvalidKeyException e) {
				e.printStackTrace();
			} catch (IllegalBlockSizeException e) {
				e.printStackTrace();
			} catch (BadPaddingException e) {
				e.printStackTrace();
			}
			
			return null;

	
	}
```


```
//Methode verpackt einzelnes ByteArray in mehrere, 245 Byte grosse, ByteArrays
Vector returnByteArrays(byte[] byteArray,int size){
		Vector inputByteArrays = new Vector();
		int tp = ((int)(byteArray.length/size));
		for(int i = 0; i<=((int)(byteArray.length/size));i++){
			if(!(byteArray.length-(size*i)>245)){
				byte[] newArray = new byte[byteArray.length-(size*i)];
				for(int j=0; j < byteArray.length-(size*i);j++){
					newArray[j]=byteArray[size*i+j];
				}
			}
			else{
				byte[] newArray = new byte[size];
				for(int j=0; j < size;j++){
					newArray[j]=byteArray[size*i+j];
				}
			}
			inputByteArrays.add(byteArray);
		}
		return inputByteArrays;
	}
```

So.. und das scheint auch gut zu klappen..
Als verschlüsselte Nachricht erhalte ich :


```
ByteBuffer buffer = ByteBuffer.allocate(50);
charset = Charset.forName( "ISO-8859-1" );
ByteBuffer decrypt;
buffer.put(charset.encode(nachricht));
decrypt = encodeWithRSA(buffer,keyPair.getPublic(),RSABlockSize);
System.out.println(charset.decode(decrypt));
```
Ausgabe :
-ésIíÕ%ïº"E6ïmëNÓDûù`î[&¡K·³üïIUÒwÆúrÑ?þt7ÄÇÂ}m?J%sz?£útÁ°^\ZùRyÇÂ?¶-CVGº¡>fez5!?R"·¹Kñ?q?K!µ¾µ¢&??Gæú2¯#?Ð?×û¢?hTÈqÑ·Ê8ò[?B?þßé?<£/õ?MÛ }Ú6×v?É?¾ä0jÎ?X2o6ØänU?÷ýá,ê%!º`Àp{?õ9tÀùÎ>eI%åñåÃ¼»9éf'ÞØ¥Ò£÷«½?

nun wird das ganze wirde decheffriert.. die decodiermehtode ist ähnlich der encodiermethode;

```
ByteBuffer decodeWithRSA(ByteBuffer bufferText, PrivateKey pk,int blockSize){
		int allocate=0;
		byte[] byteArray = bufferText.array();
		byteArray = bufferText.array();
		Vector ByteArrays = returnByteArrays(byteArray,blockSize);
		Vector tmpArrays = new Vector();
		try {
		int temp = ByteArrays.size();
		for(int i=0; i < ByteArrays.size(); i++){
			cipher = Cipher.getInstance("RSA");
			cipher.init(Cipher.DECRYPT_MODE, pk);
			byte[] tmp = cipher.doFinal((byte[])(ByteArrays.get(i)));
			allocate += tmp.length;
			tmpArrays.add(tmp);
		}
			ByteBuffer outputText = ByteBuffer.allocate(allocate);
			for(int i =0; i< tmpArrays.size();i++){
				outputText.put((byte[])(tmpArrays.get(i)));
			}
			outputText.flip();
			return outputText;
			} catch (NoSuchAlgorithmException e) {
				e.printStackTrace();
			} catch (NoSuchPaddingException e) {
				e.printStackTrace();
			} catch (InvalidKeyException e) {
				e.printStackTrace();
			} catch (IllegalBlockSizeException e) {
				e.printStackTrace();
			} catch (BadPaddingException e) {
				e.printStackTrace();
			}
			
			return null;

	
	}
```
Ausgabe:

```
buffer = decodeWithRSA(decrypt,keyPair.getPrivate(),RSABlockSize);
System.out.println(charset.decode(buffer));
```
und erhalte

" die nachricht zum verschlüsseln______________________________ die nachricht zum verschlüsseln                                 __________________________________________ "

Die leerzeichen sind klar.. schliesslich war mein Bytebuffer grösser als die tatsächliche nachricht..  aber wieso erhalte ich sie auf einmal doppelt??
vielleicht kann mir ja jemand helfen?

*grüssle*
Jörg


----------



## fehlerfinder (23. Mrz 2009)

MeinerEiner hat gesagt.:


> Da bei RSA die blocklänge 245 byte betragen muss,


Ich weiß, dass dieser Thread schon URALT ist - aber kann mir evtl. trotzdem jemand die o.g. Aussage erklären? - Es geht hier um einen RSA-Schlüssel  mit eine Länge von 2048Bit (laut Code).


----------



## ice-breaker (23. Mrz 2009)

wenn ich mich recht entsinne, war es irgendwie so, dass das N = p * q die maximale Blocklänge angibt, die 2048 Bit waren soweit ich mich erinner nur für die Primzahlen.

Ich kann mich auch gerade sehr stark irren, ist schon nen ganzen Moment her


----------



## 0x7F800000 (23. Mrz 2009)

ice-breaker hat gesagt.:


> wenn ich mich recht entsinne, war es irgendwie so, dass das N = p * q die maximale Blocklänge angibt, die 2048 Bit waren soweit ich mich erinner nur für die Primzahlen.



Also, erstmal: du hast wohl _"die Anzahl der Binärstellen der Zahl N=pq gibt die Blocklänge in bits an" _sagen wollen, Blöcke der Länge N passen in keinen Rechner dieser Welt, weil N monströs groß gebaut wird.

Aber selbst mit dieser Verbesserung ist die ausage noch nicht korrekt: 
a^phi(N) = 1 mod N
gilt nämlich nur für Einheiten in Z/NZ, also Zahlen, die nicht 0 sind, und sich auch nicht durch p oder q teilen lassen. Also ist die Länge des Blocks wohl durch das Minimum der Anzahl der Stellen von p und q beschränkt, ansonsten könnte es schief gehen.


----------



## fehlerfinder (23. Mrz 2009)

Erstmal danke für die informativen Antworten.



0x7F800000 hat gesagt.:


> _"die Anzahl der Binärstellen der Zahl N=pq gibt die Blocklänge in bits an" _


Gut, das ist soweit verständlich.



> a^phi(N) = 1 mod N
> gilt nämlich nur für Einheiten in Z/NZ, also Zahlen, die nicht 0 sind, und sich auch nicht durch p oder q teilen lassen. Also ist die Länge des Blocks wohl durch das Minimum der Anzahl der Stellen von p und q beschränkt, ansonsten könnte es schief gehen.


Da ich weder Mathematiker noch Informatiker bin, wäre es klasse, wenn du das für mich nochmal etwas allgemeiner ausdrücken könntest.

Konkret:
Was ist "a", was ist "phi"?
Sind Z/NZ zwei Zahlenmengen?
Ist die Definition davon "natürliche Zahlen ungleich 0 und nicht durch p, q teilbar"?

Wenn ich dann zwei Zahlen p und q habe, z.B. zwei 78-stellige Zahlen mit einem Produkt von 155 Stellen, entspricht das also 1240Bit. Wie könnte das denn zu der im Ursprungs-Posting genannten Aussage von "maximal 254 Byte" passen?


----------



## 0x7F800000 (23. Mrz 2009)

RSA-verfahren ist im Wesentlichen dieser Satz:
Satz von Euler ? Wikipedia
der wiederum am einfachsten als Spezialfall von
Satz von Lagrange ? Wikipedia
zu verstehen ist.
Das ist bei RSA nur eben geschickt als Kryptographieverfahren umgeschrieben.
Das sind beides sehr kurze und elegante Beweise, aber als "weder- Mathematiker -noch- Informatiker" kommt man da wohl in der Notation um (das bekloppte Bildungssystem sei "dank"  )

Wie das funktioniert steht also auf dem anderen Blatt geschrieben. Als Benutzer sollte man aber wissen:
Wenn man eine Zahl x verschlüsseln und dann wieder zurückgewinnen will, muss sie mit diesem N=pq teilerfremd sein. Das ist für beliebige zahlen garantiert, die zwischen 1 und min(p,q)-1 liegen. Länger sollte man den zu verschlüsselnden Block nicht machen, weil man dann die gefahr eingeht, dass am anderen Ende nichts mehr zu rekonstruieren ist. 
Bei p und q 78-dezimalstellig wären das also 259~256 binärstellen, damit dürfte man imho blöcke von höchstens der Länge 256bits = 32 bytes entspricht 32 char-Zeichen verschlüsseln... Und du meinst also, dass man damit 256b*y*tes verschlüsseln könnte? Hmm... ???:L Verstehe ich nicht :bahnhof:


----------



## fehlerfinder (23. Mrz 2009)

Danke für die Links - jetzt kann ich immerhin mit dem "phi" was anfangen.



0x7F800000 hat gesagt.:


> Bei p und q 78-dezimalstellig wären das also 259~256 binärstellen


aaah - jetzt habe ich endlich meinen Denkfehler gefunden: eine 155-stellige Zahl besteht natürlich mitnichten aus 155 Bytes und infolgedessen macht eine Berechnung 155 * 8Bit = 1240Bit natürlich auch überhaupt keinen Sinn...



> Und du meinst also, dass man damit 256b*y*tes verschlüsseln könnte? Hmm... ???:L Verstehe ich nicht :bahnhof:


Nein, nein, ich meinte gar nicht, sondern der Themeneröffner meinte vor knapp vier Jahren, dass RSA maximal 245Bytes auf einmal verschlüsseln kann. Und das erschien mir so spontan nicht schlüssig.

Eine mögliche Erklärung wäre die Folgende:
Ursprünglich war von einem Schlüssel mit 2048Bit die Rede, was dann ein p bzw. q mit 310 Stellen und ein N mit 618 Stellen ergibt (wenn ich mir mal die Parameter der erzeugten Keys per zB keyPair.getPrivate().toString() ausgeben lasse). Diese 618-stellige Dezimalzahl ergibt dann nach der Formel ln(N)/ln(2)/8 einen Wert von 255Bytes - somit war die ursprüngliche Angabe von 245 evtl. auch noch ein Schreibfehler.

Wie auch immer - mein Informationsbedarf ist an dieser Stelle mehr als gedeckt - VIELEN DANK!!!


----------



## fehlerfinder (24. Mrz 2009)

Ich habe jetzt eine sehr pragmatische Herangehensweise gefunden, um der Begrenzung auf 245Bytes beim Verschlüsseln auf die Schliche zu kommen.

Wenn ich einen RSA-Key mit einer Länge von 2048Bit verwende und dann eine Verschlüsselung einer "langen" Nachricht (>245 Byte) vornehme, kommt sehr spontan die folgende Info:

```
javax.crypto.IllegalBlockSizeException: Data must not be longer than 245 bytes
```

Das ist eine für Nicht-Mathematiker und Nicht-Informatiker zunächst mal ausreichende Erklärung ;-)

Übrigens gilt bei Verwendung eines 1024Bit-Schlüssels eine maximale Länge von 117Bytes.

Und falls noch jemand das ursprünglich eingestellte Programm testen möchte - da hakt es an allen Ecken und Enden. Falls jemand an einer funktionstüchtigen Version interessiert ist, kann ich diese - sobald ich sie selber habe ;-) - hier einstellen. (Aber nur, wenn es entsprechendes Feedback gibt...)


----------

