PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

Anfrage: Auftragsprogrammierung

https://www.purebasic.fr/german/viewtopic.php?t=7261

Seite 2 von 2

Verfasst: 08.03.2006 19:29
von armada
so fertig...jetzt kannste testen:

Code: Alles auswählen

Structure BigVar
  w.w[128]
EndStructure

Enumeration
  #BigVar_Kleiner
  #BigVar_Gleich
  #Bigvar_Groesser
EndEnumeration

Procedure BigVar_Length(*Var.BigVar)
  Protected Zaehler
  For Zaehler = 127 To 0 Step -1
    If *Var\w[Zaehler] <> 0
      Break
    EndIf
  Next
  ProcedureReturn Zaehler
EndProcedure

Procedure BigVar_LengthBit(*Var.BigVar)
  Protected Zaehler1, Zaehler2
  For Zaehler1 = 127 To 0 Step -1
    If *Var\w[Zaehler1] <> 0
      For Zaehler2 = 15 To 0 Step -1
        If *Var\w[Zaehler1] & (1 << Zaehler2)
          Break
        EndIf
      Next
      Zaehler1 = Zaehler1 * 16 + Zaehler2
      Break
    EndIf
  Next
  ProcedureReturn Zaehler1
EndProcedure

Procedure BigVar_HexNumber2DecimalNumber(Zeichen.s)
  Protected ASCII
  ASCII = Asc(Zeichen)
  If ASCII >= 48 And ASCII <= 57
    ProcedureReturn Val(Zeichen)
  ElseIf ASCII >= 65 And ASCII <= 70
    ProcedureReturn ASCII - 55
  Else ProcedureReturn 0
  EndIf
EndProcedure

Procedure BigVar_Copy(*Var1.BigVar, *Var2.BigVar)
  Protected Zaehler
  For Zaehler = 0 To 127
    *Var2\w[Zaehler] = *Var1\w[Zaehler]
  Next
EndProcedure

Procedure BigVar_Compare(*Var1.BigVar, *Var2.BigVar)
  Protected Laenge1, Laenge2, Zaehler
  Laenge1 = BigVar_Length(*Var1)
  Laenge2 = BigVar_Length(*Var2)
  If Laenge1 < Laenge2
    ProcedureReturn #BigVar_Kleiner
  ElseIf Laenge1 > Laenge2
    ProcedureReturn #Bigvar_Groesser
  Else
    If Laenge1 <> 0
      For Zaehler = Laenge1 To 0 Step -1
        If *Var1\w[Zaehler] < *Var2\w[Zaehler]
          ProcedureReturn #BigVar_Kleiner
        ElseIf *Var1\w[Zaehler] > *Var2\w[Zaehler]
          ProcedureReturn #Bigvar_Groesser
        EndIf
      Next
      ProcedureReturn #BigVar_Gleich
    Else
      ProcedureReturn #BigVar_Gleich
    EndIf
  EndIf
EndProcedure

Procedure BigVar_HexString2Variable(Text.s, *Var.BigVar)
  Protected Laenge, Zaehler, Zwischenwert, TempText.s
  Laenge = Round(Len(Text) / 4, 1)
  For Zaehler = 1 To Laenge
    TempText = Mid(Text, ((Zaehler - 1) * 4) + 1, 4)
    Zwischenwert = BigVar_HexNumber2DecimalNumber(Mid(TempText, 4, 1)) +BigVar_HexNumber2DecimalNumber(Mid(TempText, 3, 1)) * $10 + BigVar_HexNumber2DecimalNumber(Mid(TempText, 2, 1)) * $100 + BigVar_HexNumber2DecimalNumber(Mid(TempText, 1, 1)) * $1000
    *Var\w[Zaehler] = Zwischenwert
  Next
EndProcedure

Procedure BigVar_SHL(*Var.BigVar, Anzahl)
  Protected Laenge, Zaehler, Zwischenwert
  If Anzahl <= 16
    Laenge = BigVar_Length(*Var)
    For Zaehler = Laenge To 0 Step -1 
      Zwischenwert = *Var\w[Zaehler] << Anzahl
      If Zaehler < 127
        *Var\w[Zaehler + 1] + (Zwischenwert >> 16)
      EndIf
      *Var\w[Zaehler] = Zwischenwert & $FFFF
    Next
  EndIf
EndProcedure

Procedure BigVar_SHR(*Var.BigVar, Anzahl)
  Protected Laenge, Zaehler, Zwischenwert
  If Anzahl <= 16
    Laenge = BigVar_Length(*Var)
    For Zaehler = 0 To Laenge
      Zwischenwert = (*Var\w[Zaehler] << 16) >> Anzahl
      If Zaehler > 0
        *Var\w[Zaehler - 1] + (Zwischenwert & $FFFF)
      EndIf
      *Var\w[Zaehler] = Zwischenwert >> 16
    Next
  EndIf
EndProcedure

Procedure BigVar_Addition(*Var1.BigVar, *Var2.BigVar, *Ergebnis.BigVar)
  Protected Zwischenergebnis, Zaehler, Uebertrag
  For Zaehler = 0 To 127
    Zwischenergebnis = *Var1\w[Zaehler] + *Var2\w[Zaehler]
    Uebertrag = Zwischenergebnis >> 16
    *Ergebnis\w[Zaehler] = Zwischenergebnis & $FFFF
  Next
EndProcedure

Procedure BigVar_Subtraktion(*Var1.BigVar, *Var2.BigVar, *Ergebnis.BigVar)
  Protected Zwischenergebnis, Zaehler, Uebertrag
  For Zaehler = 0 To 127
    Zwischenergebnis = *Var1\w[Zaehler] - *Var2\w[Zaehler] - Uebertrag
    If Zwischenergebnis < 0
      Uebertrag = 1
      Zwischenergebnis + $10000
    Else
      Uebertrag = 0
    EndIf
    *Ergebnis\w[Zaehler] = Zwischenergebnis & $FFFF
  Next
EndProcedure

Procedure BigVar_RandomNumber(Startwert, *Ergebnis.BigVar)
  Protected Zaehler, ende
  RandomSeed(Startwert)
  For Zaehler = 0 To Random(127)
    *Ergebnis\w[Zaehler] = Random($FFFF)
  Next
EndProcedure

Procedure BigVar_Multiplikation(*Var1.BigVar, *Var2.BigVar, *Ergebnis.BigVar)
  Protected Laenge1, Laenge2, Zaehler, Zaehler1, Zaehler2, Zwischenergebnis, Uebertrag, Tempvar.BigVar
  Laenge1 = BigVar_Length(*Var1)
  Laenge2 = BigVar_Length(*Var2)
  For Zaehler1 = 0 To Laenge1
    For Zaehler2 = 0 To Laenge2
      Zwischenergebnis = *Var1\w[Zaehler1] * *Var2\w[Zaehler2]
      Zwischenergebnis + Uebertrag
      Uebertrag = Zwischenergebnis >> 16
      Tempvar\w[Zaehler1 + Zaehler2] = Zwischenergebnis & $FFFF
    Next
    If Uebertrag
      Tempvar\w[Zaehler1 + Zaehler2 + 1] = Uebertrag
    EndIf
    BigVar_Addition(@Tempvar, *Ergebnis, *Ergebnis)
    For Zaehler = 0 To 127
      Tempvar\w[Zaehler] = 0
    Next
    Uebertrag = 0
  Next
EndProcedure

Procedure BigVar_Modulo(*Var1.BigVar, *Var2.BigVar, *Ergebnis.BigVar)
  Protected Tempvar1.BigVar, Tempvar2.BigVar, Vergleichswert, Zaehler, Laenge1, Laenge2, Differenz
  BigVar_Copy(*Var1, @Tempvar1)
  BigVar_Copy(*Var2, @Tempvar2)
  Vergleichswert = BigVar_Compare(@Tempvar1, @Tempvar2)
  If Vergleichswert = #BigVar_Kleiner
    Laenge1 = BigVar_LengthBit(*Var1)
    Laenge2 = BigVar_LengthBit(*Var2)
    If Laenge1 > (Laenge2 + 1)
      Differenz = Laenge1 - Laenge2 - 1
      For Zaehler = 1 To (Differenz - (Differenz % 16))
        BigVar_SHL(@Tempvar2, 16)
      Next
      BigVar_SHL(@Tempvar2, Differenz % 16)
      BigVar_Subtraktion(@Tempvar1, @Tempvar2, @Tempvar1)
      BigVar_Copy(*Var2, @Tempvar2)
    EndIf
    While BigVar_Compare(@Tempvar1, @Tempvar2) <> #Bigvar_Groesser
      BigVar_Subtraktion(@Tempvar1, @Tempvar2, @Tempvar1)
    Wend
    BigVar_Copy(@Tempvar1, *Ergebnis)
  ElseIf Vergleichswert = #Bigvar_Groesser
    BigVar_Copy(*Var1, *Ergebnis)
  Else
    For Zaehler = 0 To 127
      *Ergebnis\w[Zaehler] = 0
    Next
  EndIf
EndProcedure
die division durch zwei erreichst du durch BigVar_SHR(@Variable, 1)

is das ganz normal shiften, was du vielleicht kennst, auf die gesamte struktur übertragen

und jetzt have fun damit und sag mir falls es fehler gibt

mfg
armada

edit: noch was an BigVar_HexNumber2DecimalNumber geändert...

Verfasst: 09.03.2006 11:20
von Kukulkan
Hi armada,

Vielen Dank für deine Routinen. Ich habe jetzt noch folgende Probleme damit:

1. Ich muss Variablen auch wieder in HEX zurückwandeln können.
2. Ich muss grosse Dezimalzahlen (in einem String) in BigVar wandeln können.
3. Ich sollte Zufallszahlen erhalten, die kleiner als eine gegebene Primzahl (in Dezimalformat bekannt. Kann aber auch in HEX gewandelt werden) ist.

Wie schätzt Du das Tempo ein, wenn ich folgenden Code mit deinen Routinen ausstatten soll? Basis, Exponent und Modul können bis zu 2048 Bit sein.

Code: Alles auswählen

Procedure.l dhPowerMod(Basis.l, Exponent.l, Modul.l) 
  ; PowerModulo selbst berechnen, da sonst ein Überlauf eintreten könnte 
  PM.l = 1 
  Basis.l = Basis.l % Modul.l
  While Exponent.l <> 0
    If (Exponent.l % 2) = 1 ; Wenn ungerade
      PM.l = (PM.l * Basis.l) % Modul.l
    EndIf
    Basis.l = (Basis.l * Basis.l) % Modul.l
    Exponent.l = Exponent.l >> 1
  Wend
  ProcedureReturn PM.l 
EndProcedure
Ich habe mal einige Tests mit 1Mio mal einen Modulo und eine Multiplikation. Mit Longs geht das ca. 40 bis 50 Millisekunden. Mit deinen Funktionen dauert das (ohne Debugger) fast 3 Minuten (Athlon XP 2000+).

Ich denke, das ist keine akzeptable Zeit um auf eine Authentifizierung zu warten.

Fazit: Vielen Dank für deine Mühe. Ich habe, da ich auch noch Zeitruck habe, inzwischen einen Kryptoexperten mit der Erstellung einer passenden Funktion als DLL beauftragt. Der hat bereits Codes für grosse Zahlen, Primzahlen und cryptographic secure random number generators fertig daliegen und muss nur noch einzelne Aspekte berücksichtigen. Desshalb kann der das für ca. 400,- EUR zusammenbauen.

Dennoch, vielen Dank an alle die sich den Kopf zerbrochen haben.

Volker

Verfasst: 09.03.2006 14:44
von armada
achso wusste nich, dass du auf speed wert legst...dann hätte ich das ganze gleich in asm geschrieben

naja jetzt haste ja jemand gefunden

mfg
armada
Alle Zeiten sind UTC+02:00
Seite 2 von 2

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de