_   _____________________________________   _
-6-           `^°*;:,.>Securite et cartes bleues<.,:;*°^`
_____________________/¯¯¯¯¯¯¯¯¯¯maddany¯¯¯¯¯¯¯¯¯¯\_____________________
¤º°`°º¤ø,¸¸,ø¤º°`°º¤ø,¸¸,ø¤º°`°º¤ø,¸¸,ø¤º°`°º¤º°`°º¤ø,¸¸,ø¤º°`°º¤ø,¸¸,ø¤º°`°º¤ø,
5/6/2002
                        SECURITE ET CARTES BLEUES
                    par maddany@madchat.org et crilu

I. INTRODUCTION ET DISCLAIMER
II. INTRODUCTION AU RSA
III. PRELIMINAIRES MATHEMATIQUES
IV. APPLICATION A LA CARTE BLEUE
APPENDICE I. PROGRAMMES D'EXEMPLE EN JAVA
APPENDICE II. SOURCES ET BIBLIOGRAPHIE

I. INTRODUCTION ET DISCLAIMER

Bon,  on  va  commencer  par  décourager  les  SK  :  cet  article ne traite pas
directement  des  yescards et ne devrait pas vous servir à grand-chose si ce que
vous  cherchez  c'est  comment  faire  des  yescards.  Le but de cet article est
essentiellement  de  donner  un  bon  background  mathématique  qui  permette de
comprendre  le  cryptage  avec  le  RSA,  et son application à la sécurité de la
carte  bancaire.  Le  côté  pratique sera délaissé pour donner une compréhension
en  profondeur  de  l'origine  de la faille (mise en évidence par Humpich), donc
si  vous  voulez  savoir qu'est-ce que c'est que cette faille Humpich et comment
elle marche, ce texte est fait pour vous.

Les  démonstrations  mathématiques  de  la  partie  III sont de niveau maths spé
mais  n'utilisent  que  des  outils de maths sup (comprendre que c'est de niveau
maths  sup  mais  que ce n'est pas au programme de la sup), et je pense qu'elles
sont  accessibles  à  un  bon  élève de terminale S avec un peu de recherche (et
une  petite  culture  des  programmes  mathématiques  du supérieur, notamment en
algèbre).  Ces  démonstrations  ne sont pas indispensables à la compréhension de
l'article,  elles  sont  surtout  là pour les étudiants qui cherchent à aller au
fond  des  choses  ou  juste  pour les matheux curieux de savoir le fondement du
RSA.



II. INTRODUCTION AU RSA

Le  RSA  est  un  système de cryptage asymétrique basé sur un résultat d'algèbre
que    nous  démontrerons  dans  la  partie  III  (on  dit  qu'un  cryptage  est
asymétrique  quand  on  n'utilise  pas  la  même  clé  pour coder et décoder les
données,  on  parle également de cryptage à clé publique/privée; l'autre type de
cryptage est le cryptage symétrique ou à clé secrète).

Dans la théorie, le RSA fonctionne ainsi :

on prend p et q deux nombres premiers au hasard (on rappelle que les nombres
premiers)
on pose n = p*q
on prend un entier e<n qui soit différent de p et de q et premier avec
(p-1)(q-1) (càd tel que pgcd(e,(p-1)(q-1))=1)
on choisit d tel que e*d = 1 mod (p-1)(q-1) (où a mod b = a modulo b, où le
modulo de a et de b est le reste de la division euclidienne de a par b)

On appelle d l'inverse de e modulo (p-1)(q-1). On dit alors que le couple (n,e)
est la clé publique et (n,d) est la clé privée.

[Si    vous  voulez  voir  à  la  main  ce  que  peut  donner  du  cryptage  RSA
munissez-vous  d'une  calculatrice  et  d'un brouillon. Commencez avec de petits
nombres,  par  exemple p=13 et q=17, donc n=221, puis prenez par exemple e=5. Si
vous  cherchez  d  tel  que  e*d  =  1  mod  (p-1)(q-1) càd 5*d = 1 mod 24, vous
trouvez  rapidement  d=77.  On a donc généré notre clé publique (221,5) et notre
clé  privée  (221,77). Je vous conseille de trouver votre propre exemple si vous
voulez  bien  voir ce qui se passe (avec une Texas Instrument, vous aurez besoin
des fonctions mod(a,b), gcd(a,b))]

Imaginons  maintenant  que  Fermat  ait  généré une paire de clés et que son ami
Lagrange  veuille  lui  envoyer  la recette du poulet au pistou (j'espère que le
lecteur  n'écoutera  pas  les  arguments  chronologiques  et  gastronomiques des
détracteurs  de  cet  exemple  ;).  Fermat  et  Lagrange  n'aimant pas faire les
choses   comme  tout  le  monde,  ils  se  mettent  d'accord  sur  un  moyen  de
transformer  un  texte  en  nombre  et  vice versa en définissant une bijection.
Lagrange  chiffre  la  recette  du  poulet  au  pistou  (PaP pour les intimes) à
l'aide  de  sa  fonction  ce  qui  lui donne le nombre m (dit en clair), puis il
envoie  à  son  ami  le  nombre  crypté c = m^e mod n (bien entendu, Fermat aura
préalablement  communiqué  sa  clé  publique  à  Lagrange).  Fermat  retrouve le
nombre  m  en  effectuant  l'opération c^d mod n, puis il récupère la recette en
passant  le  nombre  m dans la fonction réciproque de la fonction chiffrante. La
suite  logique  du  protocole  serait un passage au marché, mais on va s'arrêter
là.

[Bon  alors  là  je  suis  sur  que  vous  me  croyez pas et pourtant ca marche.
Regardons  ce  que  ca donne avec les valeurs choisies précédemment. Attention :
le  nombre  m  à  crypter doit être plus petit que n, donc dans notre cas disons
qu'on  veut  crypter  le  message  m=42 (pour faire plaisir à cybz et tob ;). On
obtient  le  nombre  crypté  c  =  42^5  mod  221 = 9. Maintenant essayons de le
décrypter  :  9^77 mod 221 = 42, youpi ca marche :) (si votre calculatrice n'est
pas  assez  trapue  pour  faire  ca,  vous  pouvez  toujours  vous  servir de la
calculatrice  de  windows en mode scientifique ou de maple en mode commande pour
faire  leet).  Conclusion  :  lorsqu'on crypte des données avec la clé publique,
elles peuvent et doivent être décryptées avec la clé privée]

Cette    technique  de  chiffrage  prend  tout  son  sens  si  quelqu'un  essaie
d'intercepter  le  message.  Si  la  situation précédente avait eu lieu, tout le
monde  se  doute  qu'Euler  aurait  essayé  de  connaître  la fameuse recette de
Lagrange.  En  admettant  qu'il connaisse les fonctions de chiffrage-déchiffrage
de  textes  et qu'il connaisse la clé publique de Fermat, que se passe-t-il s'il
intercepte  le  message  de  Lagrange à Fermat, càd le nombre crypté c ? Eh bien
c'est  selon.  S'il  veut  récupérer le nombre en clair m, il doit faire c^d mod
n.  Mais  si  Fermat  a  été  prudent,  il  doit être le seul à connaître sa clé
secrète,  càd  d.  Euler,  qui  tient  vraiment  à connaître cette recette, peut
toutefois  retrouver  d s'il connait p et q (pour vous en convaincre, relisez la
définition  de  d).  Cela  revient  donc  à  connaître  la décomposition de n en
facteurs  premiers.  Et  c'est  là  que  ce  trouve  la  difficulté : on ne sait
toujours   pas  factoriser  de  trop  grands  nombres  en  facteurs  de  nombres
premiers.  Donc  si Fermat a choisi p et q suffisamment grands quand il a généré
ses  clés,  il  y  a de très faibles chances pour qu'Euler arrive à factoriser n
(surtout  qu'il  ne  disposait  vraisemblablement  pas  d'ordinateur). Si malgré
tout  il  y  parvient,  Euler retrouve d et peut alors décrypter le message c et
donc connaître la recette du PaP.

Cet  exemple  (qui  vaut  ce  qu'il vaut ;), montre que toute la sécurité du RSA
réside  dans  la  difficulté  de  factoriser  n  (càd  de  retrouver p et q). En
choisissant  p  et  q  très grands, on est à peu près sûr que personne ne pourra
écouter vos messages.

[Alors  là  vous  vous  dites ouais n'importe quoi ma TI-92+ elle est surbalaise
elle  va  te  factoriser  n  en moins de 2. Très bien : essayez donc la fonction
factor(n) avec

n =
251959084756578934940271832400483985714292821262040320277771378360436620207075955
562640185258807844069182906412495150821892985591491761845028084891200728449926873
928072877767359714183472702618963750149718246911650776133798590957000973304597488
084284017974291006424586918171951187461215151726546322822168699875491824224336372
590851418654620435767984233871847744479207399342365848238242811981638150106748104
516603773060562016196762561338441436038339044149526344321901146575444541784240209
246165157233507787077498171257724679629263863563732899121548314381678998850404453
64023527381951378636564391212010397122822120720357

Au  passage  si  vous  arrivez vraiment à le factoriser, contactez RSALabs parce
que  vous  venez  de  gagner $ 200.000.  Sinon prévoyez de laisser tourner votre
calculatrice/ordinateur pendant quelques décennies/siècles :) ]

Ce  qui  est  intéressant  avec  le  cryptage  asymétrique  c'est  que l'on peut
également  crypter  les  données  à  l'aide  de la clé privée et les décrypter à
l'aide  de  la  clé  publique  (donc  d'une  manière  plus générale : ce qui est
crypté  avec  une  clé  doit être décrypté avec l'autre). Si on se place dans le
cas  de  Fermat,  et  que  celui-ci a envie d'envoyer une invitation à dîner aux
membres  du  club  d'airsoft  dont  il  fait  partie, il peut donc crypter cette
invitation  avec  sa  clé  privée,  et sa clé publique étant, vous vous en serez
doutés,  publique,  tout  le monde peut décrypter son message. Mais alors à quoi
ca  sert  ce cryptage si tout le monde peut le décrypter ? A rien si vous voulez
que  votre  message soit secret, par contre mettez-vous à la place de Galois qui
fait  bien  entendu  parler du club d'airsoft précédemment cité. Celui-ci recoit
une  invitation  qu'il  décrypte  aisément,  mais  qu'est-ce  qui lui dit que ce
n'est  pas  une  mauvaise  blague  d'Euler  ? Eh bien le fait qu'il ait réussi à
décrypter  l'invitation  avec  la  clé  publique  de Fermat prouve qu'elle a été
cryptée  avec  la clé privée de Fermat et donc à priori que c'est bien Fermat et
non  Euler  qui  a  envoyé  le message (si on suppose bien sur que Fermat est le
seul  à  connaître  sa clé privée). Cette fois le message est public mais on est
assuré  de  sa  provenance  : quand on crypte un message avec sa clé publique on
dit  qu'on  le  *signe*.  Quand on décrypte un message signé avec succès, on dit
qu'on  l'*authentifie*.  Et effectivement on authentifie bien la clé qui a signé
le message, donc a fortiori son auteur.

[J'entends  déjà  vos  calculatrices  ronronnantes  prêtes à vérifier si on peut
également  crypter  les  données  dans  ce  sens.  C'est  parti  : mettons qu'on
veuille  signer  le  message  m=22,  on  récupère c = 22^77 mod 221 = 3, puis on
effectue 3^5 mod 221 = 22. Ca marche donc dans les 2 sens]

Notez  bien  que  quand  on  authentifie  un  message  signé,  on est certain de
savoir  que  c'est  la clé privée correspondant à telle clé publique qui a signé
le  message,  mais  le  postulat  "c'est  telle personne qui a signé le message"
n'est  vrai  que  si cette personne est la seule à connaître sa clé privée. Dans
notre  exemple,  si Euler a réussi à factoriser n et donc qu'il a pu générer une
clé  privée  valable  correspondant  à la clé publique de Fermat, il peut signer
des  messages  à  la  place  de Fermat et ainsi faire des bonnes blagues au club
d'airsoft de ce dernier.

Gardez  ce  dernier  exemple  en tête puisque le RSA mis en jeu dans la sécurité
de  la  carte  bleue  est précisément une signature, et qu'en fait Humpich ayant
réussi  à  factoriser la clé publique du GIE carte bancaire (la société qui émet
les  cartes  bleues),  il  a pu en déduire une clé privée correspondante et donc
générer  de  faux  messages  semblant provenir du GIE cartes bancaires (donc ici
pour  être  clair  Fermat=GIE,  Humpich=Euler,  le  club  d'airsoft  ce sont les
banques  et  Galois  c'est  un  terminal bancaire). Mais avant de détailler plus
précisément  la  sécurité  de  la carte bleue, examinons la théorie mathématique
sous-jacente au RSA.

(vous  pouvez  passer  à  la  partie  IV  si  vous ne vous sentez pas l'âme d'un
matheux, la partie suivante est facultative)



III. PRELIMINAIRES MATHEMATIQUES

Le  but  de  cette  partie est de démontrer qu'avec les hypothèses du RSA sur p,
q, n, e et d on a :

quel  que  soit l'entier m plus petit que n, c = m^e mod n => m = c^d mod n et c
= m^d mod n  => m = c^e mod n

Théorème de Lagrange :

Si  G  est  un  groupe  fini et H un sous-groupe de G, alors l'ordre de H divise
l'ordre  de  G  (l'ordre  d'un  groupe  est  égal à son cardinal) (pour avoir la
définition  et  quelques  propriétés  sur  les  groupes,  je  vous  conseille de
chercher  un  site ou un livre sur l'algèbre de 1er cycle (les-mathematiques.net
ou le HPrépaMath Algèbre peuvent vous être utiles))

Preuve  : soit  G  un groupe  fini  et H  un  sous-groupe de  G.  On définit  la
relation R ainsi :

Pour  tout  (x,y) élt de G², on a xRy <=> x'*y élt de H où x' est l'inverse de x
cette  relation  est  une relation d'équivalence (cela se montre aisément) si on
note  xH  l'ensemble  {  x*h | x élt de H } (classe à gauche de x), alors il est
direct  que  la classe d'équivalence de x pour la relation R est xH. les classes
d'équivalences  sur  G  ainsi  définies  ont  toutes  le  même  cardinal, car la
fonction f qui à tout élt h de H associe l'élt x*h de xH est une bijection,

Donc pour tout x de G on a card(xH) = card(H)

On  en  vient au théorème de Lagrange à proprement parler : on sait qu'il existe
un  entier  naturel  n et x_1,...,x_n n élts de G tels que { x_iH | i élt de {1,
...,  n}  }  soit  une  partition  de  G, or les ensembles x_iH ont tous le même
nombre  d'éléments  card(H),  donc  on  récupère  card(G)  =  n*card(H),  ce qui
revient à dire que l'ordre de H divise l'ordre de G, CQFD

note  :  selon  la  légende,  le petit Lagrange aurait démontré ce théorème à 10
ans devants les élèves de l'école polytechnique. C'est énervant hein ;)

Corollaire du théorème de Lagrange :

Si G est un groupe et g un élt de G d'ordre fini alors l'ordre de g divise
l'ordre de G

Preuve :
posons  n  = ordre(g) (càd n est le plus petit entier naturel tel que g^n = e où
e est le neutre pour *)

L'ensemble  {  e,  g,  ...,  g^(n-1)  }  est  un sous groupe de G d'ordre n (les
savants  l'appellent  le  groupe  engendré par g :), donc d'après le théorème de
Lagrange n divise l'ordre de G.

Prop : a inversible dans Zn <=> pgcd(a,n) = 1

Preuve :
se démontre à l'aide de l'ami Bezout : un sens est trivial, l'autre l'est moins
(life is unfair)

On  travaille  maintenant  dans Z/nZ, que l'on va noter Zn pour économiser votre
bande  passante  (petit  rappel pour les idiots, les enfants et les femmes, pour
n entier naturel non nul, Zn = { k élt de N | k <= n })

Notons  phi  la  fonction indicatrice d'Euler définie ainsi : pour tout n élt de
N*, phi(n) = card({ a élt de N | pgcd(a,n) = 1 }) = card({ a élt de Zn | a
inversible dans Zn })

Théorème d'Euler :
pour tout a inversible dans Zn, on a : a^phi(n) = 1 mod n

Preuve :
notons  A  l'ensemble des éléments inversibles de Zn, on a donc phi(n) = card(A)
et (A,*) est un groupe
posons p = ordre(A)

Soit  a  élt de A, on sait que ordre(a) divise ordre(A), donc il existe k élt de
N tel que p = k*ordre(a)

On  a  donc  a^phi(n)  =  a^p  = a^(k*ordre(a)) = (a^ordre(a))^k = 1^k = 1 mod n
(attention, on travaille dans Zn donc à chaque fois on applique mod n au
résultat d'un calcul)


Théorème chinois :
si p et q sont deux nombres premiers, alors Zpq et Zp*Zq sont isomorphes

preuve :
on  montre  aisément  que  la  fonction f qui à tout élément n de Zpq associe (n
mod p, n mod q) est un isomorphisme

Extension du théorème d'Euler aux éléments non inversibles de Zn :
pour tout x de Zn et pour tout k de N on a x^(1+k*phi(n)) = x

preuve :
soient p et q deux nombres premiers, et soit n = p*q

Soit  x  élt de Zn, et f la fonction définie dans la preuve du théorème chinois.
Si  x  est  inversible  dans  Zn,  alors  la  propriété  découle  directement du
théorème  d'Euler.  Supposons  maintenant que x n'est pas inversible dans Zn, on
a  alors  pgcd(x,n)  !=  1  donc il existe d tel que d|x et d|n (si on note | la
relation "divise"), donc il existe d tel que d|x et (d|p ou d|q)
or p et q premiers donc il existe d tel que d|x et (d=p ou d=q)
donc  p|x  ou  q|x  de  manière  exclusive (car si on avait p|x et q|x on aurait
x>=pq càd x>=n, ce qui est contradictoire avec la définition de Zn)
pour fixer les idées, supposons que q|x, donc x = a*q
on a alors

f(x)^(1+k*phi(n)) = (x^(1+k*phi(n)) mod p, x^(1+k*phi(n)) mod q)
                  = (x*(x^phi(n))^k mod p, 0)
                  = (x mod p, 0)
                  = f(x)

notons f' la fonction réciproque de f, on a alors :
f'(f(x)^(1+k*phi(n))) = f'(f(x)) = x
et d'autre part, comme f' est un morphisme :
f'(f(x)^(1+k*phi(n))) = f'(f(x))^(1+k*phi(n)) = x^(1+k*phi(n)), CQFD

Application au RSA :
Placons nous dans le cadre du RSA :
soient p et q deux nombres premiers, n = p*q
soit e un nombre entier strictement inférieur à n
soit d un nombre entier tel que e*d = 1 mod (p-1)*(q-1)

Observons  que  phi(n)  = phi(p*q) = phi(p)*phi(q) = (p-1)*(q-1) car p et q sont
premiers (relisez la définition de la fonction phi si cela ne vous semble pas
immédiat)

soit  m  un  entier  strictement  inférieur à n, posons c = m^e mod n et A = c^d
mod n
il s'agit de vérifier que A = m :

A  =  c^d mod n = (m^e)^d mod n = m^(e*d) mod n = m^(1+k*phi(n)) mod n = m mod n
= m car m<n
On arrive donc bien au résultat souhaité. On peut observer si on pose c = m^d
mod n, alors on a bien m = c^e mod n.


IV. APPLICATION A LA CARTE BLEUE

Je  sens  que  la  plupart  d'entre  vous se disent "ah, on entre dans le vif du
sujet"  :)  Je  pense que les plus observateurs d'entre vous auront remarqué que
la  carte  bleue  est  une  carte  à  puce  (elle  comporte  également une bande
magnétique  et  toutes  sortes  d'informations intéressantes mais on ne traitera
ici  que  la puce), mais vous êtes-vous déjà demandé ce qu'était une puce ? Pour
faire  simple,  on  peut  dire  qu'une  puce  est un ordinateur, elle possède un
processeur,  de  la RAM, de la ROM, un système d'exploitation basique (qui a dit
windows  ?  allez tu sors) et des ports d'entrée sortie. Oui tout ca sur ce ptit
truc.  Les  anciennes  cartes  étaient  dotées  de  mémoire  EPROM  qui saturait
lorsqu'elle  était  pleine  (les  gros  acheteurs devaient alors faire remplacer
leur  carte  bleue), aujourd'hui les cartes bleues sont dotées de mémoire EEPROM
réinscriptible  de  l'ordre  de la dizaine de Ko qui permet d'éviter ce genre de
désagrément.

La  mémoire  d'une  carte  à  puce  fonctionne  à  peu  près  comme  celle d'une
disquette,  il  existe différentes zones mémoires dont les autorisations d'accès
changent  (il  peut  exister  des  zones  libres  en lecture/écriture, des zones
libres  en  lecture  qui exigent la présentation d'un code secret pour débloquer
l'écriture,  des  zones  interdites  en lecture et en écriture...). Si vous êtes
aventuriers,  vous  pouvez  acheter  un  lecteur de carte à puce pour pc (ils se
branchent  en  générale  sur  le  port  série  ou  parallèle) pour environ 100€,
personnellement  je  trouve  celui de basiccard.com assez intéressant. Bref, une
fois  que  vous  disposerez  de ce lecteur et des informations nécessaires (dans
le  livre  PC  et  cartes  à puces de Patrick Gueulle par exemple), vous pourrez
vous  amuser  à  explorer  votre  carte  :  voir  les  données publiques qu'elle
contient, y écrire vos propres données...

Pour  mieux  comprendre  la  faille Humpich, examinons à quoi ressemble un achat
effectué   par  carte  bleue  (je  simplifie  la  plupart  des  étapes  pour  ne
m'intéresser  qu'à  la  faille  humpich,  mais  la  totalité  de  la transaction
bancaire est également intéressante à étudier) :

1/ Introduction de la carte dans le terminal
Ce    dernier    alimente  alors  la  puce  de  votre  carte  puis  commence  la
communication avec elle

2/ Authentification de la carte
Dans  cette  étape, le terminal va tenter de s'assurer que votre carte n'est pas
une  carte  frauduleuse,  càd  qu'elle  a  bien  été  émise  par  le  GIE cartes
bancaires.  Il  va alors demander à la carte de lui transférer un certain nombre
de  données  :  une  Valeur d'Identification VI et une Valeur d'Authentification
VA.  Ces  deux  informations  sont  publiques, c'est pourquoi le lecteur n'a pas
besoin  de  votre code PIN pour les récupérer (vous avez peut-être déjà remarqué
que    directement  après  l'introduction  de  la  carte  le  lecteur  affichait
"authentification").  La  Valeur d'Identification contient des informations vous
concernant  :  le nom du porteur de la carte (càd vous), le numéro à 16 chiffres
imprimé  sur  la  carte,  sa  date  de  validité  et la devise de la carte (donc
maintenant  en  euros).  La  Valeur d'Authentification est un message crypté sur
320  bits,  et c'est là qu'interviennent nos remarques préliminaires sur le RSA,
car  VA  est  en  fait  un  message signé par le GIE carte bancaire (donc crypté
avec  sa  clé  privée).  Dans  le cas de la carte bleue, le terminal dispose des
informations publiques suivantes (et donc nous aussi) :

n =
213598703592091008239502270499962879705109534182641740644252416500858395774644508
8405009430865999

e = 3
c = VA

Donc  rappelez-vous,  si on veut décrypter c, on fait m = c^e mod n. A ce stade,
le  terminal  est donc censé avoir décrypté votre VA, il compare alors la valeur
m  obtenue  avec  VI,  si  m  est constitué de manière redondante d'informations
contenue  dans  VI  alors  le terminal sait que m a été crypté par la clé privée
du  GIE,  et  le  GIE  étant  censé être le seul à connaître sa clé privée votre
carte est reconnue comme valide (càd émise par le GIE).

3/ Entrée du code PIN
C'est  à  ce  stade  que  le  terminal  va  vous  demander  votre  code PIN pour
débloquer  en  écriture la zone secrète de votre carte à puce pour... y inscrire
l'historique  de  la  transaction,  càd la date et le montant de la transaction.
Tadaaaa...  Vous  vous demandez pourquoi l'historique des transactions se trouve
dans  la  zone  secrète  ? Moi aussi. Et là vous vous dites que le code PIN doit
forcément  servir  à  quelque  chose  de  plus  important  ? La réponse est non.
Conclusion  de  cette  étape  :  on peut dire que le code PIN ne sert à rien, en
tout cas il n'intervient pas dans la sécurité de la carte bleue.

4/ Calculs DES pour l'impression des facturettes
Vous  avez  peut-être  déjà entendu parler de clés DES contenues dans les cartes
bleues   :  c'est  exact  mais  elles  ne  servent  que  pour  l'impression  des
facturettes  (vous  savez  les  petits  tickets qu'on vous rend avec votre carte
bleue  et  dont  les  méchants  voleurs  de  numéros à 16 chiffres raffolaient).
Conclusion  de  cette  étape : ces calculs cryptographiques ne servent presque à
rien,  en  tout  cas  ils n'interviennent pas dans l'attaque que nous expliquons
ici.

5/ Validation de la transaction
Si  toutes  les  étapes  précédentes  ont  été  passées  avec  succès (ainsi que
quelques  autres  dont  je  n'ai  pas  besoin  de  parler dans le cadre de cette
attaque),  la  transaction  est  validée. Le monsieur ou la dame vous rend votre
carte et vous vous en allez, le coeur léger.

Maintenant que nous avons vu comment se déroulait une transaction normale,
nous  pouvons  voir  plus dans le détail ce qui se passe avec la faille Humpich.
Je  vous  ai  dit  au paragraphe II qu'Humpich avait réussi à factoriser le n du
GIE cartes bancaires. Voilà ce qu'il a obtenu :

p = 1113954325148827987925490175477024844070922844843
q = 1917481702524504439375786268230862180696934189293

Vous  pouvez  vérifier  que  p*q  est bien égal au n donné précédemment. Si vous
vous  souvenez  de  mes petits exemples avec Fermat et Euler, je vous ai dit que
si  on  connaissait  la  factorisation  de  n  en  facteurs  premiers on pouvait
retrouver la clé privée d. Eh bien faisons le :
on sait qu'on doit avoir e*d = 1 mod (p-1)(q-1), ce qui signifie e*d = 1 +
k*(p-1)(q-1), on doit donc avoir
d = (1+k*(p-1)(q-1))/e avec k tel que d soit entier
faisons l'essai avec k=1, on obtient

d =
213598703592091008239502270499962879705109534182338597041485083258128268130273720
1380241573831865/3

d n'est pas entier donc k=1 ne convient pas, essayons avec k=2 :

d =
1423991357280606721596681803333085864700730227882257313609900555054188454201824
Cette  fois  d  est entier, nous avons donc une valeur convenable qui peut faire
office de clé privée. Autrement dit, la valeur que vous venez de voir est la
privée du GIE cartes bancaires.

Maintenant  imaginons  que  vous  soyez un méchant fraudeur, disposant de la clé
privée  d,  vous  pouvez  générer de fausses Valeurs d'Authentifications. Autant
avant  vous  ne  pouviez  que  clôner  des  cartes  dans des cartes vierges pour
débiter   le  compte  de  votre  malheureuse  victime,  maintenant  vous  pouvez
carrément  créer  de  fausses  informations  ex  nihilo,  par exemple dans votre
carte  vierge  vous inscrivez la Valeur d'Identification que vous voulez (au nom
d'Ulysse  31  par exemple, avec un numéro à 16 chiffres bidon), puis vous formez
un  message  m  à  partir  des  informations de votre VI de telle sorte que vous
obteniez  une  valeur  VA  sur  320  bits,  puis vous l'inscrivez dans la carte.
Imaginez  que  vous faites un achat avec une telle carte, si vous reprenez les 5
étapes  précédentes  vous  allez  vous  rendre  compte  qu'elles  seront  toutes
passées  avec  succès  et que donc il est possible d'effectuer un achat avec une
carte  à  puce  ne  correspondant  à  aucun  compte  et même à un nom fictif. La
faille  est  donc  démontrée,  et  si on fait une rétrospective, on se rend bien
compte que toute la sécurité du RSA repose sur la difficulté de factoriser n.

Sa  clé  ayant  été  cassée,  le GIE a réagi mais pas forcément de la manière la
plus  adaptée  : il a généré une nouvelle paire de clés et donc une nouvelle VA.
Seulement  au  lieu  de  remplacer  le  jeu  de clés cassé par le nouveau jeu de
clés,  les  deux  cohabitent sur les cartes émises depuis novembre 99, càd qu'il
y  a  toujours la VA sur 320 bits codée avec la clé cassée ainsi qu'une VA codée
sur  720  bits  avec  la  nouvelle clé privée. La nouvelle VA n'est utilisée que
par  un  certain  type  de  terminaux,  donc  la  faille  restera  partiellement
effective  tant  que  toutes  les  cartes  contenant  une clé cassée ne sont pas
expirées,  càd  jusqu'en  2004  normalement.  On  aurait  pu s'attendre à ce que
toutes  les  cartes  bleues soient remplacées et que le jeu de clé cassé ne soit
plus  utilisé,  mais  le GIE a choisi une autre stratégie, sûrement pour essayer
d'étouffer l'affaire.

Voilà, vous savez (presque) tout sur la faille Humpich.


APPENDICE I. PROGRAMMES D'EXEMPLE EN JAVA

L'architecture   du  RSA  est  relativement  simple  à  implémenter,  voici  une
structure  simple  en  java qui permet de générer des paires de clés, crypter et
décrypter    des   nombres.  Si  vous  voulez  faire  un  programme  fonctionnel
permettant  de  crypter  et décrypter des messages de n'importe quelle longueur,
il  faudra  que  vous  programmiez vos fonctions de transfert texte -> nombre et
nombre  ->  texte,  pensez  également  que  les nombres que vous cryptez doivent
être  plus  petits que n. Si votre texte transformé en nombre est plus grand que
n,  une  solution  possible  est de décomposer ce nombre en base n et de crypter
séparément  chacune  de  ses  composantes,  je vous laisse vous débrouiller pour
retrouver le texte original :)

/**********BEGIN RSAEngine.java************/
import java.math.*;
import java.util.*;

public class RSAEngine {
    Random r;
    public final static int PRIME_BITS = 1024;

    public RSAEngine() {
        r = new Random();
    }

    public static void main(String[] arg) {
        RSAEngine engine = new RSAEngine();
        System.out.println("generating key pair...");
        RSAKeyPair keypair = engine.generateKeyPair();

        System.out.println("n = "+keypair.getProduct().toString());
        System.out.println("d = "+keypair.getPrivateExponent().toString());
        System.out.println("e = "+keypair.getPublicExponent().toString());

        System.out.println("key pair generated. Encoding your input");
        BigInteger m = new BigInteger(arg[0]);
        BigInteger c = m.modPow(keypair.getPublicExponent(),keypair.getProduct());
        System.out.println("ciphertext = "+c.toString());
        BigInteger clear = c.modPow(keypair.getPrivateExponent(),keypair.getProduct());
        System.out.println("decoded text : "+clear.toString());
    }

    public RSAKeyPair generateKeyPair() {
        BigInteger p = generateBigPrime(PRIME_BITS);
        System.out.println("p = "+p);
        Thread sleeper = new Thread();
        sleeper.start();
        try {
            sleeper.sleep(1000);
        } catch(InterruptedException e) {}
        BigInteger q = generateBigPrime(PRIME_BITS);
        System.out.println("q = "+q);
        BigInteger n = p.multiply(q);
        BigInteger e = generatePublicExponent(p,q,n);
        BigInteger d = generatePrivateExponent(p,q,e);
        return new RSAKeyPair(new RSAPrivateKey(n,d), new RSAPublicKey(n,e));
    }

    public static BigInteger generateBigPrime(int numbits) {
        BigInteger big;
        Random ran = new Random();
        while(true) {
            big = new BigInteger(numbits, ran);
            if(big.isProbablePrime(7) && big.isProbablePrime(20)) break;
        }
        return big;
    }

    public BigInteger generatePublicExponent(BigInteger p, BigInteger q, BigInteger n) {
        BigInteger e;
        BigInteger prod = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
        while(true) {
            e = new BigInteger(8, r);
            if(e.compareTo(n)<0 && gcd(e, prod).equals(BigInteger.ONE)) break;
        }
        return e;
    }

    public BigInteger generatePrivateExponent(BigInteger p, BigInteger q, BigInteger e) {
        BigInteger d;
        BigInteger prod = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
        System.out.println("prod = "+prod);
        BigInteger i = BigInteger.ONE;
        while(true) {
            d = i.multiply(prod).add(BigInteger.ONE);
            BigInteger[] array = d.divideAndRemainder(e);
            d = array[0];
            if(array[1].equals(BigInteger.ZERO)) break;
            else i = i.add(BigInteger.ONE);
        }
        return d;
    }

    public static BigInteger gcd(BigInteger a, BigInteger b) {
        return b.equals(BigInteger.ZERO)?a:((a.max(b)).equals(a)?gcd(b,a.mod(b)):gcd(b,a));
    }
}
/***********END RSAEngine.java*************/


/**********BEGIN RSAKeyPair.java************/
import java.math.*;

public class RSAKeyPair {
    RSAPrivateKey prv;
    RSAPublicKey pub;

    public RSAKeyPair(RSAPrivateKey prv, RSAPublicKey pub) {
        this.prv = prv;
        this.pub = pub;
        if(!pub.getProduct().equals(prv.getProduct())) throw new IllegalArgumentException("invalid key pair : different n values");
    }

    public RSAPrivateKey getPrivateKey() {
        return prv;
    }

    public RSAPublicKey getPublicKey() {
        return pub;
    }

    public BigInteger getPublicExponent() {
        return pub.getPublicExponent();
    }

    public BigInteger getProduct() {
        return pub.getProduct();
    }

    public BigInteger getPrivateExponent() {
        return prv.getPrivateExponent();
    }

    public void setPublicExponent(BigInteger e) {
        pub.setPublicExponent(e);
    }

    public void setProduct(BigInteger n) {
        pub.setProduct(n);
    }

    public void setPrivateExponent(BigInteger d) {
        prv.setPrivateExponent(d);
    }
}
/***********END RSAKeyPair.java*************/



/**********BEGIN RSAKey.java************/
public class RSAKey {}
/***********END RSAKey.java*************/



/**********BEGIN RSAPrivateKey.java************/
import java.math.*;

public class RSAPrivateKey extends RSAKey {
    private BigInteger n, d;

    RSAPrivateKey(BigInteger n, BigInteger d) {
        this.n = n;
        this.d = d;
    }

    public BigInteger getPrivateExponent() {
        return d;
    }

    public BigInteger getProduct() {
        return n;
    }

    public void setPrivateExponent(BigInteger d) {
        this.d = d;
    }

    public void setProduct(BigInteger n) {
        this.n = n;
    }

    public String toString() {
        return "("+n.toString()+","+d.toString()+");";
    }
}
/***********END RSAPrivateKey.java*************/


/**********BEGIN RSAPublicKey.java************/
import java.math.*;

public class RSAPublicKey extends RSAKey {
    private BigInteger n, e;

    RSAPublicKey(BigInteger n, BigInteger e) {
        this.n = n;
        this.e = e;
    }

    public BigInteger getPublicExponent() {
        return e;
    }

    public BigInteger getProduct() {
        return n;
    }

    public void setPublicExponent(BigInteger e) {
        this.e = e;
    }

    public void setProduct(BigInteger n) {
        this.n = n;
    }

    public String toString() {
        return "("+n.toString()+","+e.toString()+");";
    }
}
/***********END RSAPublicKey.java*************/






APPENDICE II. SOURCES ET BIBLIOGRAPHIE

http://www.parodie.com/humpich
http://dslab.csie.ncu.edu.tw/~lucas/rsamath.HTM
http://nuts.citeglobe.com/indexrsa.htm
http://www.rsasecurity.com/rsalabs/faq/
http://www.les-mathematiques.net
PC et cartes à puces - Patrick Gueulle
Cartes à puces - Patrick Gueulle
Cours de cryptographie - Gilles Zémor

Explications  de  wolf (wolf@madchat.org) et de mon prof de maths que je ne vais
pas citer pour lui éviter des problèmes ;)

Le mot de l'ami Schneier :

"You  see  smart  cards are used as credit cards all over Europe, but not in the
United  States.  Why  ?  Because of the phone system. To combat fraud, US credit
cards  went  to  an  online  verification  system.  When  you buy something, the
merchant  checks  the  validity  of  your  card  (and  the  availability of your
credit)  via  modem.  In  Europe 15 years ago that type of system would not have
worked  in  every  country.  Phones were expensive; many stores didn't even have
one,  and  the average wait time for installation in Italy was one or two years.
Phone  calls  were  expensive  and  the connections were unreliable. Fielding an
online  system  in  Europe  was expensive, so the credit card industry went with
smart  cards  to  give  some  measure of security for the transaction. It wasn't
that  smart  cards  were more secure than magnetic stripe cards, it was that the
US  solution  to  the  problem  of  fraud  -  online  verification  -  was  less
practical.  Some  intense  lobbying by the European smart card vendors (Bull SA,
Gemplus, and Schlumberger) didn't hurt, either." Secrets & Lies






        maddany@madchat.org

¤º°`°º¤ø,¸¸,ø¤º°`°º¤ø,¸¸,ø¤º°`°º¤ø,¸¸,ø¤º°`°º¤º°`°º¤ø,¸¸,ø¤º°`°º¤ø,¸¸,ø¤º°`°º¤ø,