exposant négatif dans l'exponentiation modulaire pour RSA

Question

J'essaie d'écrire un code RSA dans python3.6 à des fins éducatives.

La génération de clé et le cryptage des messages fonctionnent correctement, mais j'ai un problème avec le déchiffrement. Si je comprends l'algorithme de décryptage est M = C ^d mod n, où M est le message, C est le message crypté (en utilisant la clé publique du récepteur), d est la clé privée du récepteur. Le problème est quand d est négatif, ce qui dans mon expérience est très souvent. J'utilise un algorithme de droite à gauche pour l'exponentiation modulaire, mais je ne sais pas comment le faire fonctionner avec un exposant négatif. Voici mon code pour m. e .:

def mod_pow(b, e, m): 
if m == 1: 
    return 0 
res = 1 
b = b % m 
while e > 0: 
    if e % 2 == 1: 
     res = (res * b) % m 
    e = e >> 1 
    b = (b * b) % m 
return res 

Answer 1

La question a été répondu par James K Polk, je viens d'avoir à l'ajouter au code d'algorithme d'Euclide étendu:

if t < 0: 
    t += n