Entwickler-Ecke :: Thema anzeigen - RSA...crash ab 3 chars...

g1o2k4 - Mi 11.06.08 18:26
Titel: RSA...crash ab 3 chars...

hi

ich hab hier ein komisches phänomen...es geht ums rsa verfahren:
ich gebe buchstaben ein "test" und wandele sie in ihre ascii werte um, diese werden dann aneinander gereiht: 116101115116
zeichen die einen kleineren ascii wert als 100 haben bekommen noch eine 0 vorne dran damit immer 3er blöcke vorhanden sind außer vielleicht beim ersten.
097115 wird zu 97115

diese ascii werte verschlüssele ich mit rsa und ner square & multiplay funktion die mir jemand hier aus dem forum gab...
zum entschlüsseln wird wieder rsa angewandt und anschließend die ziffernfolge 116101115116 von hinten ausgewertet und wieder zurück in characters gewandelt: 116 101 115 116 -> "test"

es funktioniert auch tadellos, aber sobald ich mehr als 3 zeichen nehme, bekomme ich seltsame ergebnisse heraus... also "test" geht schon nicht mehr. nur "tes".

die rsa funktion, in der ich den fehler vermute sieht wie folgt aus:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

function RSA_Algorithm_BigInt(m, k, n: TBigNumber): TBigNumber; stdcall;
  //RSA-Algorithmus.
const
  C: array[0..7] of Byte = ($01, $02, $04, $08, $10, $20, $40, $80);
var
  i, j: Integer;
begin
  Result := BMD_StrToBigNum('1', false);
  for i := High(k) downto 0 do
  begin
    for j := 7 downto 0 do
    begin
      Result := BM_Modulo(BM_Multiply(Result, Result), n);
      if (k[i] and C[j]) > 0 then
        Result := BM_Modulo(BM_Multiply(Result, m), n);
    end;
  end;
end;

sollte man vielleicht auch noch die integer variablen in bigint umwandeln ?

116101115116 wäre ja die basis von rsa also "m" in der funktion...gibts da vielleicht ne mathematische beschränkung dass die basis nicht größer als x sein muss ? oder kleiner als die schlüssel ? allerdings hatte ich es auch mit größen schlüsseln probiert das klappte auch nicht.

Sirke - Mi 11.06.08 18:40

Diese Funktion ist die auf den Forum zum Square-and-Multiply!

Diese Funktion ließt keine Zahlen/Buchstaben ein. In der Funktion, wo du die Buchstaben in Dezimalblöcke umwadelst wird eher der Fehler liegen. AUßerdem um was für einen Fehler handelt es sich!

g1o2k4 - Mi 11.06.08 19:34

ich übergebe 116101115116 als bigint zahl...

der fehler sieht so aus:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

Keyparameter:
e: 689508271
d: 689789431
n: 768871039


tes:
116101115
Geheimresultat: 134631460
Klarresultat*: 116101115
Klarresultat: tes

test:
116101115116
Geheimresultat: 196396794
Klarresultat*: 1588227
Klarresultat: Lã

bei test stimmt das klarresultat* was die rsa funktion durch entschlüsselung von 196396794 liefert nicht...es müsste 116101115116 sein und nicht 1588227 und so stimmen auch die buchstaben die herauskommen nicht mehr.
am meiner funktion kanns nicht liegen, denn "tes" geht ja. alles über 3 characters geht nicht.

Sirke - Mi 11.06.08 19:46

Achso, das liegt an der Modulo Arithmethik und ist das, was ich in dem anderen Topic angesprochen habe, dass man testen muss, dass eine zu verschlüsselnde Zahl ncht größer ist als N!

116101115116 mod 768871039 = 1588227

Also ist das Resultat richtig, weil die zu große Zahl erst Reduziert wird und eben 1588227 ergibt und dann erst verschlüsselt wird! Daher MUSS man aufpassen, dass eine zu verschlüsselnde Zahl nicht größer gleich N ist! Das ist eben genau das, was ich im anderen Topic angesprochen habe!

g1o2k4 - Do 12.06.08 15:20

auch mit größerer zahl N geht es nicht....:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

Keyparameter:
e: 3109084439332534950025427953072169777
d: 6249615929756286115240101717245738561
n: 7258568330871977901193486845346641473

116101115116
Geheimresultat: 183456640
Klarresultat*: 130239494
Klarresultat: ‚ïî

116101115116 < 7258568330871977901193486845346641473 woran liegt es dass auch das nicht geht ?

Sirke - Do 12.06.08 16:23

Okay, dass ict nun sehr merkwürdig :S Ich würde aber dennoch sagen, dass es nicht am S&M liegt - nicht nur, weil es von mir ist ^^

Kannst du mal bitte den gesamten Code posten der relevant hier für ist? Man müsste das mal als ganzes sehen, weil eventuell e und d nicht die richtigen Voraussetzungen haben oder so!

Abgesehen davon, bekomme ich andere Ergebnisse bei den Potenzen sowohl mit e als auch mit d! Kann es ein, dass die Zahlen immer geschnitten werden, weil eig. sollten Zahlen rauskommen, die ungefähr die selbe Länge wie N haben. Alles andere ist bei so großen Zahlen eher unwahrschinlich...

g1o2k4 - Do 12.06.08 17:31

also bei extrem großen rsa keys, bekomm ich beim verschlüsseln mit deiner funktion auch fehler, also richtige meldungen (exceptions), aber das ist ja jetzt erstmal egal.

der relevante code:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:

procedure TForm1.Button5Click(Sender: TObject); // verschlüsseln
var temp1,temp2: string;
    i: integer;
    c: TBigNumber;
    a, b: TDateTime;
begin
  a := Time();

//....
//schlüssel währen oder erzeugen...
//....

  temp1 := Memo1.Text; // klartext
  temp2 := '';

  if Memo1.Text = '' then
    exit;

  for i := 1 to length(temp1) do  // char to ascii und aneinanderreihen
  begin
    if ord(temp1[i])<100 then
      temp2 := temp2 + '0' + inttostr(ord(temp1[i])) // mit 0 ergänzen bei z.b. a - 97
    else
      temp2 := temp2 + inttostr(ord(temp1[i]));
  end;

  Memo2.Lines.Add(temp2);


  c := BMD_StrToBigNum(temp2, false);  
  c := RSA_Algorithm_BigInt(c,
            BMD_StrToBigNum(inttostr(RSAKey.e), false),
            BMD_StrToBigNum(inttostr(RSAKey.n), false)); // rsa

  geheimtext := BMD_BigNumToStr(c, false);

  b := Time();

  Memo2.Lines.Add('Geheimresultat: ' + geheimtext);
  Memo2.Lines.Add('Zeit: ' + FormatDateTime('hh:nn:ss:zzz', b - a));
end;

procedure TForm1.Button6Click(Sender: TObject); // entschlüsseln
var temp1,temp2: string;
    i: integer;
    c: TBigNumber;
    a, b: TDateTime;
    zeichen: String;
    ca: char;
begin
  a := Time();
  klartext := '';
  temp1 := '';
  temp2 := '';

  c := BMD_StrToBigNum(geheimtext, false);  
  c := RSA_Algorithm_BigInt(c,
            BMD_StrToBigNum(inttostr(RSAKey.d), false),
            BMD_StrToBigNum(inttostr(RSAKey.n), false)); // rsa

  temp1 := BMD_BigNumToStr(c, false);

  Memo2.Lines.Add('Klarresultat*: ' + temp1); // sollte wieder ascii zeichen aneinander sein

  i := length(temp1);
  while i >= 2 do      // zeichen außeinanderfriemeln und in char wandeln
  begin
    if i <> 2 then  // alle zeichen außer evtl dem ersten ist 3 stellig...
    begin
      zeichen := '';
      zeichen := zeichen + temp1[i-2];
      zeichen := zeichen + temp1[i-1];
      zeichen := zeichen + temp1[i];
      klartext := klartext + char(strtoint(zeichen));
      i := i-3;
    end
    else
    begin // wenn das erste zeichen 2stellig ist dann das hier machen...
      zeichen := '';
      zeichen := zeichen + temp1[i-1];
      zeichen := zeichen + temp1[i];
      klartext := klartext + char(strtoint(zeichen));
      i := i-2;
    end;
  end;
  

  for I := 1 to round(length(klartext)/2) do   // buchstaben vertauschen
  begin                                        // "tset" -> "test"
    ca := klartext[i];
    klartext[i] := klartext[length(klartext)-i+1];
    klartext[length(klartext)-i+1] := ca;
  end;


  b := Time();

  Memo2.Lines.Add('Klarresultat: ' + klartext);
  Memo2.Lines.Add('Zeit: ' + FormatDateTime('hh:nn:ss:zzz', b - a));
end;

g1o2k4 - Do 12.06.08 17:51

update:

du hattest doch recht...ich hab die schlüsselvariablen vertauscht und RSAKey statt RSAKeyBigInt genommen... jetzt geht es mit message < N thx bis hierhin...

aber das problem bleibt...wenn ich mehrere zeichen gleichzeitig verschlüssele z.b. immer 4 wie entschlüssele ich es dann am ende ?
z.b. testtesttesttest

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Keyparameter:
e: 24716244657612530013569592689744784191
d: 25368224633685894810579450616838803631
n: 33411103028095097782740660751762424899

116101115116116101115116
Geheimresultat: 17977178220017450664261212587896545448
Zeit: 00:00:00:038
Klarresultat*: 116101115116116101115116
Klarresultat: testtest
Zeit: 00:00:00:032

das ergibt ja mit testtesttesttest: 1797717822001745066426121258789654544817977178220017450664261212587896545448
wie bekomm ich das auseinander um daraus wieder 17977178220017450664261212587896545448 und 17977178220017450664261212587896545448 zu machen ?

Sirke - Do 12.06.08 21:12

Wie gesagt, mit einer festen Länge! Dazu eignen sich zwar am besten Bits, aber auch wenn man das dazimal alles dartsllen möchte geht das natürlich. N hat eine feste Länge, dann müssen alle Zahlen auf diese Länge erweitert werden, indem man sie am anfang mit 0en auffüllt. Beim Trennen muss man nur wieder Blöcke der selben Länge einzelen und entschlüsseln!

g1o2k4 - Do 12.06.08 22:26

Sirke hat folgendes geschrieben:

wieso der selben länge ? wenn man sie mit nullen auffüllt haben sie doch unterschiedliche längen...
aber das prinzip ist klar. thx

Sirke - Do 12.06.08 22:29

Natürlich muss man sie so mit Nullen auffüllen, dass sie die selbe Länge erhalten:

Quelltext

1:
2:
3:
4:
5:
6:

g1o2k4 - Do 12.06.08 22:59

jo klar. wenn man z.b. sowas hat:

Quelltext

1:
2:
3:
4:

00002340
00238473
=
0000234000238473

liest man einfach von hinten die zahl mit length(modul) aus und dann die nächste usw oder ? oder muss ich mich an den 0en orientieren ?

Sirke - Fr 13.06.08 06:45

g1o2k4 hat folgendes geschrieben:

liest man einfach von hinten die zahl mit length(modul) aus und dann die nächste usw oder ?

So ist das genau richtig!

g1o2k4 - Fr 13.06.08 10:21

hier kannste mal testen...

einfach was eingeben (linkes memo feld)
dann encrypt klicken -> dann steht das verschlüsselte und kodierte (worauf es ja ankam) rechts...
dann decrypt klicken -> dann wird der entschlüsselte text links hingeschrieben.

wenn nicht passiert nicht wundern, dann hats geklappt.
bei mir ist bis jetzt noch kein müll rausgenommen, ihr könnte ja mal grenzfälle testen.

ihr könnt ja mal folgendes testen:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

das hier ins rechte memo feld eingeben:
0393749869182350877726258606702611312284095900123415253036700779889993697622011520165484947142233177022591880359133812359050943268690110016432218752445305

mit folgenden Keyparametern:
e: 14712994059481979830450293138039465033382350701814543372572716325995851300667 (zum entschlüsseln unwichtig)
d: 5954769344471165705637524839138400965083151976580016060718226260718570182083
n: 20653876287675336357910366329428390406198890481585681533349337906852656333017

wobei e oben links, d oben mitte und n oben rechts ist

anschließend auf decrypt klicken...was kommt raus ?

Martok - So 15.06.08 12:27

Quelltext

1:	0954164607944824487470088106471842218257531291451279403808427313038769283932818201542454890065101042574502164561290336805200789827960576019962835352217066

Copy&Paste ist fast schon schwierig, wenn in einem der numerischen Eingabefelder noch ein Leerzeichen rumsteht kommt nur noch müll raus. Sonst ganz nett ;)

g1o2k4 - So 15.06.08 13:03

ja das stimmt schon...aber es soll ja auch nichts professionelles sein ^^
ansonsten könnte ich gleich alles in assembler schreiben damit die performance auch stimmt :P