from os import chdir
chdir("C:/Users/Fabien/Documents/Bellevue/Informatique/eleves/S3")


Secret_depart="""Bravo, tu as trouvé la clef apparemment !
Tu as pu constater que deux clefs privées conviennent.
Tu peux répondre à la question suivante :

13.
Quelle clef ai-je utilisé pour crypter mon texte ? Là encore deux valeurs sont possibles.

Voici quelques éléments qui n'ont pas été exposés jusqu'ici :
L'entier n doit être le produit de deux nombres premiers distincts p et q : n = pq.
La valeur de n est publique, mais en pratique p et q sont très grands (supérieurs à 10300). On ne connaît pour l'instant aucun algorithme permettant à un ordinateur actuel, même puissant, de déterminer p et q à partir de n.
Si p et q sont connus, alors on peut décrypter le texte. En effet la valeur de la clef publique c est connue, il reste à déterminer celle de la clef privée d. Ces deux clefs sont reliées par la relation suivante :
Le reste de la division euclidienne du produit cd par (p -1)(q - 1) est égal à 1.
(On note φ(n) = (p - 1)(q - 1), c'est l'indicateur d'Euler de n.)
Par exemple pour n = 259, on a 259 = 7*37, donc p = 7 et q = 37 quitte à les inverser. Alors (p - 1)(q - 1) = 6*36 = 216, ce qui explique la valeur 216 donnée par l’énoncé précédemment !
Cette détermination de d connaissant c est possible en temps raisonnable par les ordinateurs actuels.

14.	
On pose  p = 6 311 et q =9 743, puis c = 38 397 531.
Écrire un programme déterminant la clef privée d associée en testant toutes les possibilités, i.e., pour d allant de 1 à (p - 1)(q - 1).
Donner le résultat.
Répondre à la même question avec p = 68 351 et q = 92 893, puis c = 4 857 201 829.
Répondre à la même question avec p = 652 429 et q = 936 527, puis c = 453 710 465 897.

Ne pas attendre la fin de l'opération !
On constate bien qu'il est nécessaire d'avoir un algorithme plus efficace.
Cet algorithme existe, c'est l'algorithme d'Euclide étendu. Voici son fonctionnement :
Les variables r, s, u, v reçoivent les valeurs respectives c, φ(n), 1, 0.
Tant que s est strictement supérieur à 0, calculer q le quotient de la division euclidienne de r par s, puis remplacer
- r, s par s, r - qs
- u, v par v, u - qv.
À l'issue de la boucle, d = φ(n) + u contient la valeur souhaitée.

15.	
Programmer cet algorithme.

16.	
On pose p = 652 429 et q = 936 527, puis c = 453 710 465 897.
Déterminer la clef privée d à l'aide de l'algorithme défini ci-dessus.
Répondre à la même question avec p = 688 257 281 et q = 954 592 879, puis c = 468 972 057 559 384 321.
"""

Secret2=Cryptage(Secret_depart,n,709)

f=open('Secret.txt','wt',encoding='utf-8')
for i in Secret2:
    f.write(i)
f.close()