Datentypenumwandlung

[Carsten1975]

Hallo zusammen,

nach jahrelanger Programmierung in diversen Sprachen bin ich wieder zu meiner alten Lieblingssprache Pascal zurückgekehrt.

Nun bin ich gerade dabei einige Vorbereitungen für ein neues Projekt zu treffen und auszuprobieren.
Was hierbei natürlich ziemlich wichtig ist, ist dabei die Umwandlung von Datentypen bei Rechenoperationen.
Ich habe schon viel gelesen aber ich denke, dass ich irgendwo einen Denkfehler mache, aber vielleicht könnt ihr mir ja helfen.

Hier mein Beispiel in Kurzform:

var_n1_int : integer = 109493;
var_z1_int : integer = 72;
var_z2_int : integer = 101;

const_E_flt : float = 19;

var_Block_dbl := Power((var_z1_int + (256 * var_z2_int)), const_E_flt); <--- Ergebnis: 7,2712879331751834011197048660147e+83


soweit funktioniert es auch, aber die Werte werden schon gerundet was nicht sein darf.

Zudem sollte es eigentlich so heißen:

var_Block_int := Trunc(Power((var_z1_int + (256 * var_z2_int)), const_E_flt) mod var_n1_int); <--- Ergebnis: 22496 <--- funktioniert nicht, nur Fehlermeldungen!


und hier bekomme ich ziemliche Probleme, zumal die Werte auf keinen Fall abgeschnitten bzw. gerundet werden dürfen und es hier schon mal zu Zahlen mit 100 bis 200 Stellen kommen kann.

Ich habe das Ganze auch schon mit extended ausprobiert, aber auch hier gab es die Probleme.

Vielleicht könnt ihr mir da ja weiterhelfen.

Carsten

[compmgmt]

Mod funktioniert erst ab FPC 3.1.1 mit Gleitkommazahlen.

http://wiki.freepascal.org/Mod

Oder halt selbst machen:

In older versions of FPC that support operator overloading you can add this feature yourself. Here's an example for double precision modulo.

Code: Alles auswählen

operator mod(const a, b: double) c: double; inline;
begin
  c:= a - b * Int(a / b);
end;

[wp_xyz]

zumal die Werte auf keinen Fall abgeschnitten bzw. gerundet werden dürfen und es hier schon mal zu Zahlen mit 100 bis 200 Stellen kommen kann.

Selbst mit dem Datentyp Extended hat man nur so an die 20 gültige Stellen, also: es werden auf jeden Fall Stellen abgeschnitten. Falls das wirklich ein Problem ist (was ich für die meisten Rechnungen anzweifle), musst du dir eine "Big-Number"-Bibliothek suchen. Vielleicht solltest du beschreiben, was du eigentlich machen willst.

[Carsten1975]

Danke für eure Antworten.

Werde mal weitersuchen in den tiefen des Internets.

Es geht hier um eine RSA-Verschlüsselung


Wen es interessiert, mit der Bibliothek GNURZ geht es.

[af0815]

Genau dafür gibt es Bibliotheken wie GNURZ. Ich weis nur aktuell nicht ob die Version sich noch mit Lazarus 2.0 kompilieren lässt. Mal testen.

[Warf]

So als erstes einmal solltest du etwas über Fließkommazahlen (Float, Single, Double, Extended) wissen, die haben fehler. Dargestellt werden die Zahlen nach dem IEEE 754 Standard, das bedeutet, eine Zahl besteht aus einem Sign Bit s, einer Mantisse m und einem exponenten e. Eine zahl wird dann dargestellt als 0,m * 2^e * (-1*s). Beispiel, die Zahl 2 hat den exponenten 2, als mantisse 0,5 (in dezimal, binär natürlich 0,1) und das sign 0 (da es positiv ist). Damit ergibt sich 2 = 0,5 * 2^2 * (-1*0). Das bedeutet aber, egal wie lang die Mantisse ist, man kann akkurat nur zahlen darstellen die sich als zweierpotenz darstellen lassen. 1/3 zum beispiel wird im zweiersystem (wie auch im dezimalsystem) als periode dargestellt 0,01010101010... (dezimal: 0,33333...), und kann daher im IEEE 754 nicht dargestellt werden.

Nicht nur bei Kommazahlen haben sie fehler sondern auch bei großen Zahlen. Extended hat eine Mantisse von 64 Bit, einen exponenten von 15 bit (insgesamt also 80 bit. lustige geschichte wie es zu der zahl kam, tut hier aber nix zur sache), Du kannst also jede 64 bit ganzzahl darstellen (du schreibst sie einfach in die mantisse und setzt den exponenten auf länge der mantisse), darüber wird es aber extrem löchrisch. Nehmen wir mal 5 bit, 2 bit mantisse, 2 bit exponent, dann gibt es die zahlen 0, 0,5 0,25, 0,75 die direkt über die mantisse darstellbar sind. außerdem ist für jede dieser zahlen x auch x*2^{0, ..., 3} verfügbar (in echt ists etwas komplizierter aber fürs beispiel solls reichen). Das wars, alle zahlen die dar durch nicht abgedeckt sind exsistieren in dem system nicht, und es wird auf die nächste exsistierende zahl gerundet

Die Rundungsfehler aus dem IEEE 754 lassen sich dennoch gut handhaben, und solang man damit leben kann (z.B. bei numerischen Approximationen) ist das alles kein Problem. Du willst aber Crypto machen, darfst daher keine Fließkommazahlen verwenden, da rundung für dich tödlich ist.

Die einfache alternative währe wohl Integer zu nehmen, aber da erreichst du keine Sicherheit. Für RSA auf elliptischen Kurven benötigt > 200 bit für Cryptografische Sicherheit, auf Ganzen zahlen (wie ich denke das du es implementierst) werden 2000 bit vorgeschlagen, das kannst du nicht mehr auf Integer typen realisieren. Du benötigst also eine Big Int library.

Aber darf ich fragen wofür du das machst? wenn du es wirklich als sicherheitsmechanismus einbauen möchtest ist hier mein tipp: lass es und benutz ne gute fertige implementation wie openSSL oder PGP.
Deine implementierung wird langsamer und vor allem unsicher sein.

Zwei kleine beispiele. RSA ist nur so sicher wie der Zufallszahlen generator. in der OpenSSL war mal ein Bug das die Zufallszahlen nicht ganz zuffällig waren. Man hatte zwar nur eine sehr kleine treffer wahrscheinlichkeit, bei genug versuchen hat es irgendwann aber funktioniert die Primfaktorzerlegung zu knacken und damit war die gesammte TLS verschlüsselung für diese verbindung hinfällig. (Und das ist Profis passiert, du bist wahrscheinlich kein profi)
Das andere beispiel ist, um effizienter RSA auszurechnen verwendet man für gewöhnlich den Chinesischen Restsatz, wonach man statt m^e mod n in zwei schritten erst m^e mod p und m^e mod q ausrechnet und dann durch einen einfachen trick m^e mod n daraus berechnen kann. Grundsätzlich auch echt genial, somit muss man statt 2000 bit arithmetik nur 200 bit arithmetik ausrechnen und ist damit mindestens einen faktor 10 schneller. Studenten von berkley (war es glaube ich) ist es dann aber gelungen einen sidechannel attack durchzuführen. Wenn es gelingt eine der beiden unterschritte (z.B. m^e mod p) einen falschen wert ausrechnen zu lassen, so kann man gcd(m-m', n), m ist die orginal message, m' die falsch dekodierte) ausrechnen und das ist dann entweder p oder q.

An sowas denkt man als laie nicht, und schwups hat man statt einer sicheren verschlüsselung plötzlich lediglich eine performance fressende funktion die keine echte sicherheit bietet.

[Carsten1975]

Es gaht darum dass ich die Auflage vom Finanzamt bekommen habe, bestimmte Felder in einer Datenbank von einem Kassensystem mit einer RSA-Verschlüsselung zu codieren. So dass niemand an der Datenbank die Summen manipulieren kann. Wenn ich das nachweisen kann, dann erhält die Software wieder die Finanzamtzertifizierung.

D. h. es geht hier nicht um große Daten, sondern lediglich um die Daten von den einzelnen Kassenbons in einzelnen Datenbankfeldern.

Aber ich habe die Vorgabe für eine RSA-Verschlüsselung.

Im Grunde ist es mir bewußt, dass ich hier überhaupt keine sichere Verschlüsselung erstellen kann, denn anhand des Kassenbons kenne ich ja die einzelnen Positionen und somit auch die Summe. Was zwangsläufig dazu führt, dass ich weiß was drinne steht und wie es jetzt aussieht. Somit ist eine Decodierung immer möglich, aber erzähl mal das dem Finanzamt. Die nach 12 Jahren Entwicklungszeit und Kosten in Höhe von 2,5 Millarden Euro es aufgegeben haben in Deutschland eine einheitliche Steuersoftware für das Finanzamt entwickeln zu lassen.


Gnurz funktioniert noch unter 2.0.

[Warf]

Ja gut da kannst du dann auch nichts machen.

Dann benutz einfach GNURZ, damit hab ich mir auch schon mal ne RSA verschlüsselung zusammen gebastelt, es hat gut funktioniert, die hat auch direkt die Funktionen zum Exponieren modulo und zur Primzahlgenerieren, auch wenn der Random algorithmus nicht cryptografisch sicher ist. Damit ist RSA implementieren sehr einfach