[Java] RSA Implementierung

[snow]

Guten Abend,

ich mache momentan ein wenig auf dem Gebiet der Kryptographie und habe zusammen mit einem Freund mal den RSA Algorithmus implementiert. Das ganze ist relativ schlampig geschrieben und für eine richtige Verwendung muss natürlich noch einiges angepasst werden.

Bezout.java:

 Spoiler

public class Bezout
{
	int a = 0;
	int b = 0;
		
	public Bezout(int a, int b)
	{
		this.a = a;
		this.b = b;
	}
		
	private int ggT(int a, int b)
	{
		if (a == 0) return b;
		else if (b == 0) return a;
		else
		{
			int remainder = 0;
			do
			{
				remainder = a % b;
				a = b;
				b = remainder;
			} while (remainder != 0);
		}
			
		return a;
	}
		
	public int getD()
	{
		if (a == 0) return 0;
		else if (b == 0) return 1;
		else
		{
			int s1 = 1, s2 = 0, s = 0;
			int t1 = 0, t2 = 1, t = 1;
				
			while (a % b != 0)
			{
				int q = a / b;
				int r = a % b;
					
				s = s1 - q * s2;
				t = t1 - q * t2;
					
				s1 = s2; s2 = s;
				t1 = t2; t2 = t;
				
				a = b;
				b = r;
			}
				
			return s;
		}
	}
}

PublicKey & PrivateKey:

 Spoiler

public class PublicKey
{
	public int n;
	public int e;
}
	
public class PrivateKey
{
	public int n;
	public int e;
	public int p;
	public int q;
	public int d;
	public int phi;
}

RSA.java:

 Spoiler

public class RSA {
	
	private PublicKey pk = new PublicKey();
	private PrivateKey sk = new PrivateKey();
	
	public RSA()
	{
		generate();
	}
	
	public List<Integer> encrypt(String m)
	{
		List<Integer> c = new ArrayList<Integer>();
		
		for (char ch : m.toCharArray())
		{			
			BigInteger i = BigInteger.valueOf(ch);
			i = i.modPow(BigInteger.valueOf(pk.e), BigInteger.valueOf(pk.n));

			c.add(i.intValue());
		}
		
		return c;
	}
	
	public String decrypt(List<Integer> c)
	{
		StringBuilder m = new StringBuilder();
		
		for (int ch : c)
		{		
			BigInteger i = BigInteger.valueOf(ch);
			i = i.modPow(BigInteger.valueOf(sk.d), BigInteger.valueOf(sk.n));
			m.append((char)i.intValue());
		}
		
		return m.toString();
	}
	
	private void generate()
	{	
		SecureRandom sr = new SecureRandom(String.valueOf(new Date().getTime()).getBytes());
		int random_1 = Math.abs(BigInteger.valueOf(Math.abs(sr.nextInt()) % 0x7FFF).nextProbablePrime().intValue());
		int random_2 = Math.abs(BigInteger.valueOf(Math.abs(sr.nextInt()) % 0x7FFF).nextProbablePrime().intValue());
		int random_3 = Math.abs(BigInteger.valueOf(Math.abs(sr.nextInt()) % 0x7FFF).nextProbablePrime().intValue());
			
		while (random_3 == random_1 || random_3 == random_2)
		{
			random_3 = Math.abs(BigInteger.valueOf(Math.abs(sr.nextInt()) % 0x7FFF).nextProbablePrime().intValue());
		}
		
		sk.p = random_1;
		sk.q = random_2;
		
		sk.n = sk.p * sk.q;
		pk.n = sk.n;
		
		sk.phi = (sk.p - 1) * (sk.q - 1);
		sk.e = random_3;
		pk.e = sk.e;

		sk.d = new Bezout(sk.e, sk.phi).getD();
	}
}

Verwendung:

RSA r = new RSA();
List<Integer> e = r.encrypt("Hallo, das ist ein Test!");
String d = r.decrypt(e);
System.out.println(e);
System.out.println(d);

Output:

[7484230, 25519014, 16496664, 16496664, 4431689, 30090520, 18294078, 24305863, 25519014, 19679855, 18294078, 23172419, 19679855, 19597773, 18294078, 17379383, 23172419, 25257367, 18294078, 19783768, 17379383, 19679855, 19597773, 1102907]
Hallo, das ist ein Test!

Formal sieht das ganze so aus:

encrypt: m x eKey -> c
decrypt: c x dKey -> m

Evtl. lernt jemand ja was dadurch.

[Lord iRemix]

Nice one.

MfG

[BigJk]

Moin, hab da noch ein paar kleine Anmerkungen ^^ Ich weiß nicht wie weit du in dem Thema bist, daher kann es sein das ich dir jez nur Sachen sage die du eh schon weißt.

1.

Warum hast du in deiner PrivateKey Klasse noch Phi, p, q. Diese werden doch nur während der Key Generation gebraucht.


2.

Ich würde dir empfehlen die Nachrichten beim Ent- und Verschlüsseln in Blöcke zu teilen, so werden die Nachrichten kleiner.

Du kannst ja Zahlen bis zu der Größe von n verschlüsseln, also kannste ja sowas machen:

Angenommen n = 110

Du willst z.B. 'ABCDE' verschlüsseln. Wir gehen dabei mal davon aus das A die Zahl 1 repräsentiert usw. und das wir nur Buchstaben im Alphabet verschlüsseln und ohne Groß- und Kleinschreibung.

Somit haben wir dieses Alphabet: 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' und unsere höchste Zahl wäre die 26 ( 26 = Z )

In n passt die 26 mind. 4 mal rein. Somit können wir bis zu 4 Zeichen in einem verschlüsseln.

Also teilen wir 'ABCDE' in 'ABCD' und 'E' wandeln dies in eine Zahl um:

'01020304' und '05'

Diese Blöcke verschlüsselt man nun.


3.

encrypt: m x eKey -> c
decrypt: c x dKey -> m

Das stimmt so nicht.

Encrypt: m ^ e % n = c
Decrypt: c ^ d % n = m

( '^' steht hier für das Potenzieren )

Im Programm selber machst du es aber wieder richtig indem, da du ModPow benutzt...

4.

Was soll Bezout heißen und warum hast du da ne Funktion drinnen zum ggT ermitteln und benutzt sie nit?


So, ich denke das wars, falls ich mich selber irgendwo vertan habe oder du noch Fragen hast werde ich diese gerne beantworten

[snow]

Heyho,

1) korrekt, die werden nur zur Generierung gebraucht, ich wollte es nur in der Klasse haben, da das ganze ja das veranschaulichen sollte, was ich in der Theorie gelernt habe - private Eigenschaften und öffentlich bekannte Eigenschaften. Kann man in einer "richtigen" Implementierung eigentlich auch vernachlässigen, korrekt.

2) danke für den Tipp

3) Das ganze sollte eigentlich eher den Ablauf der Funktion an sich darstellen, encrypt wendet die Parameter m und eKey auf sich an und resultiert in c, bei decrypt dann c und dKey, das in m resultiert. Hatte noch überlegt, ob ich die eigentliche Funktion definiere, da wäre dann m ^ e % n = c natürlich richtig.

4) Das ganze ist das Lemma von Bézout (Lemma von Bézout ? Wikipedia), so erhalte ich den privaten Key für die Entschlüsselung. Die ggT Funktion wird eigentlich gar nicht benötigt, ich hatte davor eine andere Klasse geschrieben, daraus ist dann die Bézout Klasse entstanden. Einfach ignorieren.

Das Buch, das ich verwende, ist übrigens dieses hier:

[BigJk]

1. Ok

2. Jo kein ding ^^

3. Ist halt nur nicht klar ersichtlich das du das meinst und ich denke jemand der keine Ahnung davon hat erkennt das noch weniger.

4. Aso, hatte nicht dran gedacht das das damit zusammen hängen könnte xD Hab selber bisher zum Modularen Inverse bestimmen immer den Erweiterten Euklidischen Algorithmus genutzt, hatte mich dahingehend nicht mit anderen Algorithmen beschäftigt ^^