ElGamal Signature ( version standard ) en quelques lignes:

Parametres:
- un nombre premier p,
- g et x aléatoires, inferieurs a p 
- y = g^x mod p 

clef publique = (y, g, p) 
clef privée   = x 

Calcul de la signature de M:
Choix d ’un nombre aléatoire k ( k et p-1 premiers entre eux )

                  r = g^k mod p
                  s = inv(k) * (M - x*r) mod (p-1)
 

Vérification de la signature (r,s):
                  v1 == v2 avec v1 = g^M mod p  et  v2 = y^r * r^s mod p
 

  La solidité de cette signature repose sur le fait qu'il est difficile de calculer des logarithmes discrets, c'est a dire que pour des valeurs suffisament grande il est impossible,  dans un temps raisonnable, de determiner x  grace à la relation: y = g^x mod p... 

Analyse du code:
  Recherche des GetDlgItemTextA ( api utilisé pour recuperer les valeurs saisie )...
  A partir de là, le code de la source n'etant pas protegé il suffit d'observer ce qu'il se passe:
 

Complete le Nom avec des '*' ( 2Ah )  afin que celui comporte au  moins 1Eh caracteres:

_text:004010F8 PaddingName: 
_text:004010F8                 cmp     esi, 1Eh            ;  cmp Longueur du nom, 1Eh 
_text:004010FB                 mov     eax, esi 
_text:004010FD                 jge     loc_0_401124        ; si Longueur >= 1Eh
_text:004010FF                 mov     edx, 1Eh            ; sinon
_text:00401104                 lea     edi, [ Name + esi]  ; pointe a la fin du nom
_text:0040110A                 sub     edx, esi
_text:0040110C                 mov     eax, 2A2A2A2Ah
_text:00401111                 mov     ecx, edx
_text:00401113                 mov     ebx, ecx
_text:00401115                 shr     ecx, 2
_text:00401118                 repe stosd                   ; et copie des 2Ah 
_text:0040111A                 mov     ecx, ebx             ; afin que celui si comporte 1Eh caracteres
_text:0040111C                 and     ecx, 3
_text:0040111F                 repe stosb

_text:004011B1 Majuscule: 
_text:004011B1                 mov     al, byte ptr [Serial1 + edx]
_text:004011B7                 cmp     al, 41h
_text:004011B9                 jl      short Minuscule
_text:004011BB                 cmp     al, 5Ah
_text:004011BD                 jle     short CheckFormatSerial
_text:004011BF 
_text:004011BF Minuscule: 
_text:004011BF                 cmp     al, 61h
_text:004011C1                 jl      short Nombre
_text:004011C3                 cmp     al, 7Ah
_text:004011C5                 jle     short CheckFormatSerial
_text:004011C7 
_text:004011C7 Nombre: 
_text:004011C7                 cmp     al, 30h
_text:004011C9                 jl      short ErreurSerial
_text:004011CB                 cmp     al, 39h
_text:004011CD                 jg      short ErreurSerial
_text:004011CF 
_text:004011CF CheckFormatSerial:
_text:004011CF 
_text:004011CF                 mov     edi, offset Serial
_text:004011D4                 or      ecx, 0FFFFFFFFh
_text:004011D7                 xor     eax, eax
_text:004011D9                 inc     edx
_text:004011DA                 repne scasb
_text:004011DC                 not     ecx
_text:004011DE                 dec     ecx
_text:004011DF                 cmp     edx, ecx
_text:004011E1                 jl      short Majuscule

Ces quelques precautions prises le programme passe à la verification Name\Serial1\Serial2: ( Si je reste assez evasif sur les methodes employées pour l'analyse du code , c'est qu'elles sont tres rudimentaires:  intuition / logique / jeu avec les parametres d'entrés... )

Jusqu'a present le programme manipulait des chaines de caracteres donc le programme va effectuer la convertion chaine de caractere => nombre au format Miracl ( presence de la chaine 'MIRACL error from routine ' dans le programme ;) )

_text:00401272                 push    offset Serial1
_text:00401277                 push    ebp
_text:00401278                 call    CvrtNumMiracl 

_text:00401281                 push    offset Serial2
_text:00401286                 push    edx
_text:00401287                 call    CvrtNumMiracl 

_text:00401290                 mov     ecx, [esp+64h+PadNameSize]
_text:00401294                 push    ebx
_text:00401295                 push    offset Name
_text:0040129A                 push    ecx
_text:0040129B                 mov     dword ptr [eax+238h], 10h
_text:004012A5                 call    CvrtStringMiracl

_text:004012AA                 push    offset aAc2db4fec8c62992db4f 
_text:004012AF                 push    esi
_text:004012B0                 call    CvrtNumMiracl 

Et là surprise, les valeurs renvoyées par les 2 premiers call  ne ressemblent pas vraiment a ce qui etaient attendus, c'est d'autant plus etrange que quelques lignes plus bas tout semble fonctionner correctement... Or la seule valeur ayant changée entre les differents appels est celle se trouvant en [eax+238h], elle passe de 3Ch à 10h autrement dit de 60 à 16. "AC2DB4FEC8C62992DB4F" etant en base 16 on peut supposer que la valeur située en [eax+238h] est la base utilisée lors de la convertion chaines => valeurs numeriques... Autrement dif  les serials sont interpretés comme si ils etaient en base 60 (  ce qui est confirmé par le calcul ).

Par ordre croissant : "0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x"   ( Alors pourquoi les caracteres y et z sont sont autorisés ? ;)) )
 
 

Au vu des parametres d'entrés on peut supposer que ce call va effectuer un calcul... mais lequel ?
Le plus simple est de remplacer les differents parametres par des 0 ou des 1 et observer les effets que cela a sur la valeur resultat.

_text:004012B5                 push    ebx             ;  => NomR
_text:004012B6                 push    esi             ; "AC2DB4FEC8C62992DB4F"
_text:004012B7                 push    2               ;  2
_text:004012B9                 push    ebx             ; Nom
_text:004012BA                 call    CalculeNomR

CalculeNomR renvoit: NomR ( =  Nom^2 mod AC2DB4FEC8C62992DB4F )
 

En utilisant la meme demarche  (  l'analyse est simplifié  par le fait que l'on saut deja que l'on doit tomber sur du ElGamal)

_text:004012F3                 push    eax             ;  => Val1
_text:004012F4                 push    esi             ; B54F430648C6B2A10FFB
_text:004012F5                 push    ebx             ; NomR
_text:004012F6                 push    ecx             ; 2E0C2DB4FEC8C6299A0C
_text:004012F7                 call    powMod

Val1 = 2E0C2DB4FEC8C6299A0C ^ NomR mod B54F430648C6B2A10FFB
 

_text:00401304                 push    edx             ;  => Val 2
_text:00401305                 push    esi             ; B54F430648C6B2A10FFB
_text:00401306                 push    eax             ; Serial2_
_text:00401307                 push    ebp             ; Serial1_
_text:00401308                 push    ebp             ; Serial1_
_text:00401309                 push    edi             ; 4E0F2ACAD51C4CCDFB51
_text:0040130A                 call    sub_0_4034B0

val2 = 4E0F2ACAD51C4CCDFB51^Serial1_ * Serial1_^Serial2_ mod B54F430648C6B2A10FFB
 

_text:00401317                 push    ecx
_text:00401318                 push    edx
_text:00401319                 call    _compare            ; compare val1 et val2
_text:0040131E                 add     esp, 38h
_text:00401321                 test    eax, eax
_text:00401323                 push    0 
_text:00401325                 jnz     short loc_0_401338
_text:00401327                 mov     eax, [esp+58h+hWnd]
_text:0040132B                 push    offset aGoood       ; "GOOOD!!!"
_text:00401330                 push    offset aYourKeyIsGood_

Application de ElGamal:

On retrouve donc les equations permettant des verifier une "signature ElGamal";
                  v1 = g^M mod p
                  v2 = y^r * r^s mod p
avec
        g = 2E0C2DB4FEC8C6299A0C
       M = NomR
         p = B54F430648C6B2A10FFB
         r = Serial1_
         s = Serial2_
         y = 4E0F2ACAD51C4CCDFB51

or 
    r = g^k mod p
    s = inv(k) * (M - x*r) mod (p-1)
et
    y = g^x mod p 
 

c'est a dire 

  Serial1_ = 2E0C2DB4FEC8C6299A0C^k mod B54F430648C6B2A10FFB
  Serial2_ = inv(k) * (NomR - x*Serial1_) mod (B54F430648C6B2A10FFB-1)
et 
  4E0F2ACAD51C4CCDFB51 = 2E0C2DB4FEC8C6299A0C^x mod B54F430648C6B2A10FFB

On retombe donc sur le probleme du logarithme discret mais heureusement la taille a été limité afin que le temps de calcul de ne soit pas trop long... ( cf les remerciments ;)))

Plusieurs solutions sont possibles pour effectuer ce calcul: utiliser le programme index.c / index.cpp present dans le repertoire Source de Miracl, utiliser celui de tE! (basé sur l'index.c de Miracl) ou taper les mots "java+discrete logarithm" dans un moteur de recherche... :) 
 

Quelques minutes plus tard, on obtient:      x = 3F6536A02CD18F3B67D3 

Calcul d'une clef valide:
Plus rien nous empeche alors de calculer des Serials corrects :
 
 

Nom	Amenesia
NomPad	Amenesia********************** = 416D656E657369612A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2A
NomR	3B240DEDDB1407B14B7

En prenant k = 1 ( pourquoi se compliquer la vie ;)):
 

Serial1	2E0C2DB4FEC8C6299A0C (en base 16) => 1drmL9dBJgRSLW (en base 60)
Serial2	6AE06B269D5970281B3B    (en base 16) => 3ppd7BUub4Qnax (en base 60)

Amusez vous bien...

Remerciements :
- jB meme si il s'est ouvertement moqué de moi... enfin il y avait de quoi... ;)
Sans lui Maple serait encore entrain de tourner ;))  ( Maple a des "petits" problemes avec les logarithme discret.... )
 
- Lise Grim pour sa patience et ce qu'elle nous fait decouvrire...