|
| |
VB.NET - Fortgeschrittene| .NET und die sehr großen Zahlen | |  | | Autor: Tomahawk | | Datum: 02.09.11 14:43 |
| Hallo Leute,
heute wurde ich gefragt ob ich beim Erstellen eines kleinen Programmes helfen könnte, das per RSA einfachen Text verschlüsseln und wieder entschlüsseln soll. Klar, kein Problem!
Man soll dabei einen "öffentlicher" Schlüssel selber wählen können, nehmen wir mal für e = 247 und für N = 29. Bei der Berechnung nimmt man z.B. den ASCII-Wert eines Zeichens und potentiert diesen mit e Modulo N. Gleich beim ersten Test kracht es oder es kommt ein falsches Ergebnis heraus. Für das große A kommt als verschlüsselte Folge 155 statt 221 raus. .NET scheint irgendwie Probleme mit solch großen Zahlen zu haben. Wir reden hier über Zahlen, die locker mal 10.000-stellig werden können. Der Windows-Taschenrechner bekommt das gut hin. Doch in .NET gibt es keinen Datentyp, den ich momentan kenne, der dafür geeignet ist. String wäre eine Lösung, doch dann muss man alles zu Fuß rechnen. Das will ich eigentlich vermeiden.
Nun die Frage: Wie soll man sowas "zuverlässig" und "performant" berechnen?
Die Zeit ist der größte Feind des Menschen. | |
| Re: .NET und die sehr großen Zahlen | | | | Autor: Preisser | | Datum: 02.09.11 14:49 |
| Hallo,
seit .Net 4.0 gibt es die BigInteger-Struktur, die mit beliebig großen Ganzzahlen rechnen kann.
Man sollte aber eigentlich auch die Wertebereiche der anderen, internen Zahlendatentypen kennen, wenn man mit ihnen rechnet (z.B. Long: -2^63 bis +(2^63-1). 
Beitrag wurde zuletzt am 02.09.11 um 15:09:44 editiert. | |
| Re: .NET und die sehr großen Zahlen | | | Autor:  FZelle (Moderator) | | Datum: 02.09.11 15:41 |
| | Wer Verschlüsselung unter .NET macht, sollte auch Bouncy Castle kennen, und die haben dafür klassen. | |
| Re: .NET und die sehr großen Zahlen | | | | Autor: Snof | | Datum: 02.09.11 22:27 |
| Hallo
Wie FZelle schon gesagt hat, gibt es in .NET extra Klassen für Verschlüsselung. Eventuell ist es sinnvoller diese zu verwenden. Aber darum geht es mir gerade nicht.
Um n^p mod m auszurechnen, brauchst du kein BigInt oder etwas dergleichen.
Folgende Überlegung: Eine Modulo-Rechnung (z.B. a mod n) können wir uns so vorstellen, dass wir a Elemente gleichmäßig auf n Fächer verteilen und wissen möchten, wieviele Elemente übrig bleiben. So können wir fünf Elemente nicht gleichmäßig auf vier Fächer verteilen, sondern es bleibt eins über. Machen wir es dies zwei mal, bleiben zwei Elemente übrig. Wiederholen wir das einige Male, sind irgendwann genug Elemente übrig, um sie wieder verteilen zu können.
Diese Überlegung lässt sich nun in eine Formel packen:(a*b) mod n = ((a mod n) * b) mod n Dieser Gedanke lässt sich weiterentwickeln. Für a^p mod n rechnen wir nicht den Wert der gesammten Gleichung aus, sondern immer nur für einen Teil. Im ersten Schritt von a. Diesen Rest multiplizieren wir nun mit dem nächsten a und errechnen erneut den Rest. Das ganze wird dann p mal wiederholt.
Es ergibt sich dann folgender Code:Function PotMod(a As Integer, p As Integer, n As Integer) As Integer
Dim m As Integer = 1 'Neutrales Element der Mutiplikation
For i As Integer = 1 To p
m = (m * a) Mod n
Next
Return m
End FunctionDer höchste Wert den du nun haben kannst ist a*(n-1).
Insgesammt sind es p Schleifendurchläufe. Es geht auch mit weniger, aber ich finde gerade meine (nicht unbedingt gute) Mitschrift meiner Kryptographie-Vorlesung nicht 
Beitrag wurde zuletzt am 02.09.11 um 22:28:54 editiert. | |
| Re: .NET und die sehr großen Zahlen | | | | Autor: Tomahawk | | Datum: 03.09.11 12:20 |
| Moin moin,
Zu Frage 1 => .NET 4.0 haben wir nicht, wir nutzen noch 2.0
Zu Punkt 2 => 10.000-stellige Zahlen können bei der Nutzung "vernünftiger" Schlüssel entstehen, die Grenzen des Taschenrechners habe ich noch nicht ausgereizt...aber dieses Ergebnis 1,0597021063087308977720495167035e+9230 habe ich eben mal mit 230768^1721 ausrechnen lassen und es kommt dicht ran.
Zu Frage 3 => die schon vorhandenen Klassen in .NET zur Verschlüsselung sind etwas undurchsichtig und helfen nicht dabei die Funktionsweise oder auch die einzelnen Schritte von RSA zu lehren. Unser Azubi hat es als Hausaufgabe bekommen und er soll es selber programmieren (s. Wikipedia). Er nutzt dafür PHP. Wir wollten die Kommunikation nun Plattformübergreifend über ein Chat-Programm realisieren. Doch .NET 2.0 ist damit scheinbar "überfordert".
Werde mir mal .NET 4.0 anschauen müssen.
Die Zeit ist der größte Feind des Menschen. | |
| Re: .NET und die sehr großen Zahlen | | | | Autor: Preisser | | Datum: 03.09.11 12:40 |
| Hallo,
Tomahawk schrieb:
| Zitat: | |
die
Grenzen des Taschenrechners habe ich noch nicht
ausgereizt...aber dieses Ergebnis
1,0597021063087308977720495167035e+9230 habe ich eben mal mit
230768^1721 ausrechnen lassen und es kommt dicht ran.
| |
Ich glaube, dir fehlen da einige Grundlagen.
Eine solche angezeigte Zahl hat nicht wirklich 9000 Stellen, sondern es werden nur eine bestimmte Anzahl an Ziffern gespeichert (Mantisse), sowie um wieviel Stellen das Komma verschoben werden muss (daher der Name "Gleitkommazahl"). Eine Double beispielsweise besteht aus 1 Vorzeichenbit, 52 Mantissenbits sowie 11 Bits für die Charakteristika. Gleitkomazahlen sind somit nicht exakt, sondern stellen den Wert nur ungefähr da (siehe auch hier).
Ganzzahlen dagegen sind exakt, haben aber eben nur einen bestimmten Wertebereich, der sich aus der Anzahl der verwendeten Bits ergibt. Ein Long z.B. besteht aus 64 Bits, also kann es 2^64 Werte darstellen (durch Verwendung des Zweier-Komplements ergibt das einen Wertebereich von -2^63 bis +2^63-1).
Das hat eigenltich nichts damit zu tun, dass .Net damit überfordert wäre, sondern das liegt an den in den Prozessor eingebauten Zahlentypen. BigInteger kann zwar mit beliebig großen Zahlen rechnen, das ist aber langsamer als die Standard-Zahlentypen (vor allem, wenn mit sehr großen Zahlen gerechnet wird).
Ich kann mir allerdings auch nicht vorstellen, dass bei irgend einer Verschlüsselung solch große Zahlen entstehen würden.
Für die Berechnung (a^b mod n) mit großen b, wie sie bei RSA anfallen kann, verwendet man die von Snof beschriebene Technik (bzw. mit einer Abwandlung, dass man die erhaltenen Zahlen quadriert, damit weniger Schleifendurchläufe nötig sind), sodass die Zahlen erst gar nicht so groß werden können.
Beitrag wurde zuletzt am 03.09.11 um 13:33:12 editiert. | |
| Re: .NET und die sehr großen Zahlen | | | | Autor: Preisser | | Datum: 03.09.11 15:30 |
| Nachtrag:
Hier noch eine Variante, die binäre Exponentiation verwendet, womit bei der Berechnung von a^p mod n nur noch log2(p)+1 (abgerundet) Schleifendurchläufe notwendig sind.
Public Shared Function PotMod(a As Integer, p As Integer, n As Integer) As _
Integer ' Berechnet (a^p) mod n
Dim bits As List(Of Boolean) = GetBitsBackwards(p)
Dim m As Integer = 1
For i As Integer = bits.Count - 1 To 0 Step -1
m = m * m Mod n
If bits(i) Then m = m * a Mod n
Next
Return m
End Function
Private Shared Function GetBitsBackwards(a As Integer) As List(Of Boolean)
' gibt eine Bitliste zurück (rückwärts)
Dim l As New List(Of Boolean)
While a > 0
l.Add(a Mod 2 = 1)
a >>= 1
End While
Return l
End FunctionWie Snof bereits erwähnte, können bei einer derartigen Berechnung die Zahlen nicht so groß werden. Hier dürfte der größte Wert, der entstehen kann, Max((n-1)^2,(n-1)*a) betragen.
Beitrag wurde zuletzt am 03.09.11 um 18:42:04 editiert. | |
| Re: .NET und die sehr großen Zahlen | | | | Autor: Preisser | | Datum: 03.09.11 17:02 |
| Hallo,
ja ok, stimmt. Dafür verwendet man dann wohl tatsächlich BigInteger-artige Datentypen. Jedoch sollte man trotzdem z.b. nach jedem Multiplikationsschritt den Modulo anwenden/binäre Exponentation verwenden, damit die Zwischenergebnisse möglichst klein bleiben.
Beitrag wurde zuletzt am 03.09.11 um 17:26:48 editiert. | |
| Re: .NET und die sehr großen Zahlen | | | | Autor: Preisser | | Datum: 03.09.11 19:06 |
| Hallo,
ja, denke ich auch.
BigInteger hat sogar die statische (Shared) ModPow()-Methode, die genau die Berechnung (a^p) Mod n durchführt, vermutlich auf die geschilderte Weise (mit binärer Exponentiation usw.). ^^
Beitrag wurde zuletzt am 03.09.11 um 19:06:25 editiert. | |
 | Sie sind nicht angemeldet!
Um auf diesen Beitrag zu antworten oder neue Beiträge schreiben zu können, müssen Sie sich zunächst anmelden.
 Einloggen | Neu registrieren |
 |
|
sevISDN 1.0 
Überwachung aller eingehender Anrufe!
Die DLL erkennt alle über die CAPI-Schnittstelle eingehenden Anrufe und teilt Ihnen sogar mit, aus welchem Ortsbereich der Anruf stammt. Weitere Highlights: Online-Rufident, Erkennung der Anrufbehandlung u.v.m. Weitere InfosTipp des Monats sevOutBar 4.0 
Vertikale Menüleisten
á la Outlook
Erstellen von Outlook ähnlichen Benutzer- interfaces - mit beliebig vielen Gruppen und Symboleinträgen. Moderner OfficeXP-Style mit Farbverläufen, Balloon-Tips, u.v.m. Weitere Infos
|
Mai 2024
Sie sind aktuell nicht angemeldet.