Programmes Python interactifs pour démontrer le chiffrement RSA sur les calculatrices graphiques (TI-Nspire et NumWorks): https://github.com/alexander-henkes/rsa-calculator-python

# Chiffrement RSA: Mise en œuvre mathématique d'un processus de chiffrement complet

from math import gcd

# Test de primalité
def est_premier(n):
  """Vérifie si un nombre est premier"""
  if n<2:return False  # Les nombres inférieurs à 2 ne sont pas premiers
  if n==2:return True  # 2 est le seul nombre premier pair
  if n%2==0:return False  # Tous les autres nombres pairs ne sont pas premiers
  # Teste uniquement les diviseurs impairs jusqu'à la racine carrée de n
  for i in range(3,int(n**.5)+1,2):
    if n%i==0:return False
  return True

# Saisie d'un nombre premier avec validation
def saisie_premier(nom):
  """Invite l'utilisateur à saisir un nombre premier et valide l'entrée"""
  while True:
    try:
      nombre=int(input('Nombre premier '+nom+': '))
      if nombre<2:print(str(nombre)+' est trop petit!');continue
      if est_premier(nombre):print('Entrée valide: '+str(nombre)+' est un nombre premier!');return nombre
      else:print(str(nombre)+" n'est pas un nombre premier!")
    except:print('Entrée invalide!')

# Algorithme d'Euclide étendu
def euclide_etendu(a,b):
  """Calcule PGCD et les coefficients x, y pour a*x + b*y = PGCD(a,b)"""
  if b==0:return a,1,0
  else:g,x1,y1=euclide_etendu(b,a%b);x=y1;y=x1-a//b*y1;return g,x,y

# Calculer l'inverse modulaire
def inverse_mod(e,phi):
  """Calcule l'inverse modulaire de e modulo phi"""
  g,x,y=euclide_etendu(e,phi)
  if g!=1:return  # Aucun inverse n'existe si PGCD != 1
  return x%phi

# Exponentiation modulaire (efficace)
def puissance_mod(base,exposant,module):
  """Calcule (base^exposant) mod module efficacement"""
  resultat=1;base=base%module
  while exposant>0:
    if exposant%2==1:resultat=resultat*base%module
    exposant=exposant>>1;base=base*base%module
  return resultat

# Trouver un e approprié
def trouve_e(phi):
  """Trouve un e approprié qui est premier avec phi"""
  candidats=[3,5,7,11,13,17,19,23,29,31]
  # Essayer d'abord les petits nombres premiers
  for e in candidats:
    if e<phi and gcd(e,phi)==1:return e
  # Si aucun ne convient, rechercher systématiquement
  for e in range(2,phi):
    if gcd(e,phi)==1:return e

# Convertir une lettre en nombre
def lettre_vers_nombre(lettre):
  """Convertit une lettre en nombre (A=0, B=1, ..., Z=25)"""
  lettre=lettre.upper()
  if'A'<=lettre<='Z':return ord(lettre)-ord('A')

# Convertir un nombre en lettre
def nombre_vers_lettre(nombre):
  """Convertit un nombre en lettre (0=A, 1=B, ..., 25=Z)"""
  if 0<=nombre<=25:return chr(nombre+ord('A'))

# Fonction principale: Processus RSA
def rsa():
  # Sortie: En-tête
  print('='*30);print('Chiffrement RSA');print('='*30);print()

  # ÉTAPE 1: Choisir les nombres premiers
  print('ÉTAPE 1: Choisir les nombres');print('premiers');print('-'*30)
  p=saisie_premier('p')
  # S'assurer que q est différent de p
  while True:
    q=saisie_premier('q')
    if q!=p:break
    print('Erreur: p et q doivent')
    print('être différents!')
  print('Sélectionné: p='+str(p)+', q='+str(q))
  input('Continuer avec Entrée ...');print()

  # ÉTAPE 2: Calculer n et phi(n)
  print('ÉTAPE 2: n et phi(n)');print('-'*30)
  n=p*q  # Module n = p * q
  phi=(p-1)*(q-1)  # Fonction d'Euler phi(n) = (p-1)*(q-1)
  print('n = p*q = '+str(p)+'*'+str(q)+' = '+str(n))
  print('phi(n) = (p-1)*(q-1)')
  print('phi(n) = '+str(p-1)+'*'+str(q-1)+' = '+str(phi))
  input('Continuer avec Entrée ...');print()

  # ÉTAPE 3: Déterminer la clé publique e
  print('ÉTAPE 3: Clé publique e');print('-'*30)
  print('Note: e doit être premier')
  print('avec phi(n) = '+str(phi)+', c.-à-d. (PGCD(e, phi(n)) = 1)')
  suggestion=trouve_e(phi)
  print('Suggestion: e = '+str(suggestion))
  reponse=input('Utiliser? (O/N): ')
  # L'utilisateur peut accepter la suggestion ou saisir son propre e
  if reponse.lower()=='o':e=suggestion
  else:
    while True:
      e=int(input('Utiliser e personnalisé: '))
      if e>=phi:print('e doit être < '+str(phi)+'!');continue
      if gcd(e,phi)==1:print('Entrée valide:');print('PGCD('+str(e)+','+str(phi)+')=1');break
      else:print('PGCD('+str(e)+','+str(phi)+')!=1')
  print('Clé publique: ('+str(e)+', '+str(n)+')')
  input('Continuer avec Entrée ...');print()

  # ÉTAPE 4: Calculer la clé privée d
  print('ÉTAPE 4: Clé privée d');print('-'*30)
  print('d est l\'inverse modulaire')
  print('de e mod phi(n)')
  print('d*e = 1 (mod '+str(phi)+')')
  print('Calculer avec l\'algorithme')
  print('d\'Euclide étendu:')
  d=inverse_mod(e,phi)
  print('d = '+str(d))
  # Vérification: d * e mod phi doit égaler 1
  print('Vérification: '+str(d)+'*'+str(e))
  print('mod '+str(phi)+' = '+str(d*e%phi))
  print('Clé privée: ('+str(d)+', '+str(n)+')')
  input('Continuer avec Entrée ...');print()

  # ÉTAPE 5: Chiffrer le message
  print('ÉTAPE 5: Chiffrement');print('-'*30)
  print('Chiffrement: c=m^e mod n')
  print('c = m^'+str(e)+' mod '+str(n))
  print()
  print('Codage des lettres:')
  print('A=0, B=1, C=2, ..., Z=25')
  print()
  # Saisie de lettre avec validation
  while True:
    lettre=input('Lettre (A-Z): ').strip()
    if len(lettre)==1:
      m=lettre_vers_nombre(lettre)
      if m is not None:
        if m<n:print("'"+lettre.upper()+"' = "+str(m));break
        else:print('Erreur: '+str(m)+' >= '+str(n));print('Choisir des nombres premiers plus petits!')
      else:print('Invalide! Seulement A-Z autorisé!')
    else:print('Une seule lettre!')
  # Effectuer le chiffrement: c = m^e mod n
  c=puissance_mod(m,e,n)
  print()
  print('c = '+str(m)+'^'+str(e)+' mod '+str(n))
  print('c = '+str(c))
  print('Lettre chiffrée: '+str(c))
  input('Continuer avec Entrée ...');print()

  # ÉTAPE 6: Déchiffrer le message
  print('ÉTAPE 6: Déchiffrement');print('-'*30)
  print('Déchiffrement:')
  print('m = c^d mod n')
  print('m = '+str(c)+'^'+str(d)+' mod '+str(n))
  # Effectuer le déchiffrement: m = c^d mod n
  m_nouveau=puissance_mod(c,d,n)
  lettre_nouvelle=nombre_vers_lettre(m_nouveau)
  print('m = '+str(c)+'^'+str(d)+' mod '+str(n))
  print('m = '+str(m_nouveau))
  print('Lettre déchiffrée: '+str(lettre_nouvelle))
  # Vérification: La valeur déchiffrée correspond-elle à l'original?
  if m==m_nouveau:print('Réussi!')
  else:print('Erreur!')
  input('Continuer avec Entrée ...');print()

# RÉSUMÉ: Afficher toutes les valeurs importantes
  print('='*30);print('RÉSUMÉ');print('='*30)
  print('Nombres premiers: p='+str(p)+', q='+str(q))
  print('Module (p*q): n='+str(n))
  print('Fonction phi d\'Euler: phi='+str(phi))
  print('Clé publique: ('+str(e)+','+str(n)+')')
  print('Clé privée: ('+str(d)+','+str(n)+')')
  print('Texte clair (lettre): '+lettre.upper())
  print('Texte clair (nombre): m='+str(m))
  print('Nombre chiffré: c='+str(c))
  print('Nombre déchiffré: m='+str(m_nouveau))
  print('Lettre déchiffrée: '+str(lettre_nouvelle))
  print('='*30)

# Boucle de répétition potentielle
while True:
  rsa()  # Exécuter un processus RSA
  print()
  encore=input('Relancer le calcul? (O/N): ')
  if encore.lower()!='o':print('Programme terminé!');break
  print('\n'*2)