NC imcp.ba@trousperdu.org imcp.ba@free.fr IMCP Blandy Alain
|
Vous avez des certificats partout dans votre surfeur ! A quoi et a qui ils servent ? GUIDE DE SURVIE |
|
MAIS certains surfeurs ne sont pas d'accord et exigent pour envoyer un mail crypte a un tier, que vous installiez d'abord un de vos "certificat personnel" (qui ne sert qu'a signer ou a decrypter) Pourquoi donc ! * On se retrouve donc dans un cercle vicieux (type La poule et L'oeuf ! + OSPF ?) qui conduit utilisateur a passer qu'un CA "officiel" est obligatoire !!! ??? Pour calmer votre surfeur, vous pourriez faire 5 6 7 8 et lui servir alors votre certificat P12 autosigne temporaire du 5B. Si vous venez de faire cette methode, vous constater peut etre, que votre mailleur ne veut toujour pas, utiliser ce certificat auto signe, pour seulement, signer vos mails ! Il n'a pas confiance en vous, vus qu'il n'a pas trouve autorite de CA qui va avec ! Mais chez moi, y a un leger mieux, car ce certificat de signature invalide, l'autorise a crypter ? (avec le certificat de destination public BoxLibrecert.pem du 2, aprouve par le certificat CA du 1 ) ! Et a partir de la, je peut envoyer mon mail crypte contenant en copier coller ma demande de certification !!! Mais cela ne suffit pas toujours pas a calmer, votre surfeur !, En resume votre seurfeur ne vous fait pas confiance ! il fait confiance a ces parmetrages implicites issu de chez les copains du fabricants du logiciels .... Mais il y a une soultion beaucoup plus simple (puisque vous savez utiliser des logiciels libres) : Crypter votre mail, SANS le mailleur (comme en PGP). et ensuite utiliser le mailleur pour le transmettre (sans lui dire que c'est crypte) ! Rien n'est impossible dans les logiciels libres ! Il est necessaire de bien comprendre pour commencer proprement. Pourquoi cryter le mail qui contiend votre demande de certification CSR ? Pour etre sur, que seule le CA destinataire pourra exploiter votre demande ! ( Meme les seurfeur ou le maileur que vous utiliserai pour envoyer le mail n'y comprendra rien ! ) Si votre demande est une test, qui contiend aucune data privee, c'est pas trop grave ! Mais si les infos que circulent sont confidentielles, vous pouvez avoir un soucis ! La demande de certification que vous avez faite(et lue j'espere) est independante du CA, donc n'importe qui peut y repondre et vous envoyer un certificat ... et se faire passer pour le CA original ... ou vous faire un certificat non dessire cache ... (plus vrai que vrai puisque vous l'avez signe par avance) !!!) * RQ : En fait le mime et le pk dans les couriers on beaucoup etait modifies et tous le monde n'est pas d'accord , et implement se protcole comme il peut, voir comme il veut ! : - on peut vouloir cryter un message pour un destinatire donne (sans le signer) - on peut vouloir cryter un message pour un destinatire et l'envoyer a un autre destinataire qui le relayra, sans pouvoir le lire ... - on peut vouloir le signer , sans le crypter - on peut vouloir signer et crypter un message que l'on a recus (sans le contre signe ...) - etc ..... Et si interface du programme n'est pas ergonomique ou mal concus on risque de ne pas savoir vraiment ce qu'il fait ! D'ou peu etre le fait que certain seurfeur vous demande votre certificat pour un cryptage simple alors que certificat du destinataire suffit ! et/ou decide d'utiliser votre certificat personnel en prime ! D'ou le partis pris dans ce TP de decomposser toutes les etapes avec openssl; surtout dans le cas ou l'interrese n'a aucun certificat, ( et en demande un a un CA ) ! |
|
# # Veuillez trouver ci-apres le CSR a certifier : -----BEGIN CERTIFICATE REQUEST----- MIIC+TCCAeECAQAwgbMxCzAJBgNVBAYTAkZSMRYwFAYDVQQIEw1NSURJLVBZUkVO .... .... NFMQHApCmSU5mPiXxxU0GrxR6n40oY/Zt0W5iYYDQgZDLlE6R1ZGfYsx0cdx -----END CERTIFICATE REQUEST----- # fin du fichier PEM # |
|
# # # Veuillez trouver ci-apres la copie du MAIL CODE DU CSR : To: imcp.blib@...... From: myaddresse@chezmonmailleur.bizmonmail Subject: Encrypted CSR message Mime for CA [BLIb] MIME-Version: 1.0 Content-Disposition: attachment; filename="smime.p7m" Content-Type: application/x-pkcs7-mime; smime-type=enveloped-data; name="smime.p7m" Content-Transfer-Encoding: base64 MIIHiwYJKoZIhvcNAQcDoIIHfDCCB3gCAQAxggIIMIICBAIBADCB6zCB3jELMAkG A1UEBhMCTFAxLTArBgNVBAgTJElOVEVSTkVUIExJQlJFIERBTlMgREVVWCBQQVlT .... .... o+Tx4GBlpD/wFxYE8J1HTErF/e9HhbmDq3MdNwLBpGKnvjFFz2Xsl3lXVvibweg+ IIV9e0r+CxpwKQfbPage # fin du fichier CODE # # |
|
ARNAQUE DE L'AMPOULE A ECONOMIE D'ENERGIE DES AMPOULES PLUS CHERES ET AUCUNE ECONOMIE "Une ampoule electrique a filamant, qui eclaire et qui chauffe en hiver, c'est moins con, qu'un radiateur qui chauffe sans eclairer !" Elle est ou l'economie d'enegie ? IL N'Y EN A PAS : Si j'arrete l'ampoule a filamant qui chauffe, (ou si je la remplece par une ampoule dite economique) le thermostat fera chauffer le radiateur electrique automatiquement plus longtemps ! Je payerai done la MEME consomation electrique .. et en plus, je serai dans le NOIR ! Conclusion j'achete les ampoules normales, car moins cheres (40c) ! On fait payer d'avance au con sommateur, les pretendues economies, qu'il ne fera pas en hiver (et en ete, j'allume pas la lumiere); mais on ne baisse pas le prix des isolants thermique !? Il est a noter, qu'il y a longtemps deja, des proces en Amerique on etait fait aux fabricants d'ampoules a incandescence, qui on fait une entente, pour limiter la duree de leurs ampoules a 1000 heures ! On sait, depuis longtemps, fabriquer des ampoules qui dure tres longtemps, Berlin Est en RDA a etait equipe d'ampoules jaunes (Oxram ?) ... On pourrais probablement fabriquer des ampoules a incandesence de 10.000H pour moins d'un euro ! Mais grace au lobis europeen c'est interdit, pire on fait la promotion avec de l'argent public, d'ampoules a economiee d'energie contenant du mercure ... Vous constate de par ailleurs, que dans les grandes surface, qui ne sont pas filentrope, eclairage ce fait eclairage ce fait ;principalement par tubes neon, qui sont donc probablement le moyen eclairage le plus economique (sans avoir a parler des self balast, du cosinus phi, du tris phases) ! Oui, bien sur, a l'entree du magazin (et haut dessus du rayon poissonerie , charcuterie ...) il n'y a pas de neon; mais des ampoules specialisees, (qui ne sont pas la pour economie d'energie) ! Mais Personne n'a besoin de faire de la pub publique pour les tubes neon, pourtant connus depuis longtemps comme probablement tres economique* ! ( * en 2017 on commence a voir des leds eclairage dans les nouveaux magazins! ) etc etc ..... Pire pour aider les pauvres a s'en sortir on leur propose acheter ces fausses solutions surfacturees. En fait ampoule a economie energie est peut etre interessante dans les salles climatisees ! Donc ceux qui se chauffe a electricite, et qui achetant ces ampoules, fabrique a etrange, poluantes, et trop cheres pour le moment, perde de argent et sponsorise de fait, ceux qui font marcher leur clim en ete, ( et qui n'on pas besoin etre aides ...) etc etc.... Attendez que leurs prix baissent a moins d'un euro pour 10.000h ! isoler vous meme vos murs ! De plus cette arnaque ecolo a etait promue par des campagnes de pub institutionelles payes par nos impots ! Consomateurs : pigons etc etc ..... Pour vous eclairez l'ete, attendez un peut, pour passer directement a la technolgie filament led, que l'on commence a trouver sur tous les supports de connection, a 10 000H, pour une consommation faible ... Leurs prix devrais commencer a baisser en 2017, et pourrais concurencer le filament traditionnel ! ARNAQUE ECOLO DU VEHICULE HYBRIDE LA PASTILLE VERTE SUR CES GROSSES VOITURES ... ? |
Rappel :
A modulo M ( A % M) est le reste de la division de A par M
ce reste est fatalement entre 0 et M-1
A est donc la Forme A = (A % M) + K * M (entiers)
Donc (A + B) % M = ((A % M) + ( B % M)) % M + 0 = (A % M ) + ( B % M )
Donc (A * B) % M = ((A % M) * ( B % M)) % M + 0 = (A % M ) * ( B % M )
Donc ( A % (P1 * P2) ) % P1 = A % P1
soit A % M % M % M = A % M
On vois que le % M a tendance a ce retouver un peut partous
il passe de interieur d'une expresion vers exterieurs et reciproquement
par associativite, distributivite, nilpotance ....
et donc on est tente d'ecrire :
((A^e)*(A^d))%M = (A ^(e + d)) % M
((A^e)%M)^d) %M = (A ^(e * d)) % M
En calculant des puissances sucessives de X modulo M on s'attend
a retouver le meme reste au plus toutes les M-1 operations
ou meme avant (puisque le nombre de restes est finis ) :
On vas s'interesser au puissance sucessives de X (le nombre a coder ) :
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1
2 4 8 16 32 64 128 256 512 1024 2048
3 9 27 81 243 729 2187 6561 19683 59049 177147
4 16 64 256 1024 4096 16384 65536 262144 1048576 4194304
5 25 125 625 3125 15625 78125 390625 1953125 9765625 48828125
6 36 216 1296 7776 46656 279936 1679616 10077696 60466176 362797056
7 49 343 2401 16807 117649 823543 5764801 40353607 282475249 1977326743
Ensuite on considere ces memes nombres
dans divers systemes de representation modulo :
---
soit les memes valeurs lues en modulo 2 (M=2) (phi = 1)
les colonnes veticales sont identiques : se repetent par groupe de 1
les lignes horizontales se repetent par groupe de 2
une ligne sur 2 est nulle (x multiples de 2)
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 0 0 0 0 0 0 0 0 0 0 0
3 1 1 1 1 1 1 1 1 1 1 1
4 0 0 0 0 0 0 0 0 0 0 0
5 1 1 1 1 1 1 1 1 1 1 1
6 0 0 0 0 0 0 0 0 0 0 0
7 1 1 1 1 1 1 1 1 1 1 1
---
soit les memes valeurs lues en modulo 3 (M=3) (phi = 2)
les colonnes verticales se repetent par groupe de 2
les lignes horizontales se repetent par groupe de 3
une ligne sur 3 est nulle (x multiples de 3)
une ligne sur 3 est a 1
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 2 1 2 1 2 1 2 1 2 1 2
3 0 0 0 0 0 0 0 0 0 0 0
4 1 1 1 1 1 1 1 1 1 1 1
5 2 1 2 1 2 1 2 1 2 1 2
6 0 0 0 0 0 0 0 0 0 0 0
7 1 1 1 1 1 1 1 1 1 1 1
---
soit les memes valeurs lues en modulo 4 = 2 * 2 ( M=4) (phi = 2)
les colonnes verticales se repetent par groupe de 2
les lignes horizontales se repetent par groupe de 4
une ligne sur 4 est nulle (x multiples de 4)
une ligne sur 4 est a 1
la ligne 2 est incodable presque nulle
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 2 0 0 0 0 0 0 0 0 0 0
3 3 1 3 1 3 1 3 1 3 1 3
4 0 0 0 0 0 0 0 0 0 0 0
5 1 1 1 1 1 1 1 1 1 1 1
6 2 0 0 0 0 0 0 0 0 0 0
7 3 1 3 1 3 1 3 1 3 1 3
---
soit les memes valeurs lues en modulo 5 ( M=5) (phi = 4 = 2 * 2)
les colonnes verticales se repetent par groupe de 4
ceraines lignes verticale ( ex 4) sont egale a 1 toutes les 2 colonnes
les lignes horizontales se repetent par groupe de 5
une ligne sur 5 est nulle (x multiples de 5)
une ligne sur 5 est a 1
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 2 4 3 1 2 4 3 1 2 4 3
3 3 4 2 1 3 4 2 1 3 4 2
4 4 1 4 1 4 1 4 1 4 1 4
5 0 0 0 0 0 0 0 0 0 0 0
6 1 1 1 1 1 1 1 1 1 1 1
7 2 4 3 1 2 4 3 1 2 4 3
---
soit les memes valeurs lues en modulo 6 = 2 * 3 (phi = 2)
les colonnes verticales se repetent par groupe de 2
les colonnes verticales sont egale a 1 par multiples de 2
les lignes horizontales se repetent par groupe de 6
une ligne sur 6 est nulle
une ligne sur 6 est a 1
une ligne sur 6 est a 3
une ligne sur 6 est a 4
les lignes 2 4 et 3 manquent de varitee
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 2 4 2 4 2 4 2 4 2 4 2
3 3 3 3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4 4 4 4
5 5 1 5 1 5 1 5 1 5 1 5
6 0 0 0 0 0 0 0 0 0 0 0
7 1 1 1 1 1 1 1 1 1 1 1
---
soit les memes valeurs lues en modulo 7 (phi = 6 = 2 * 3)
les colonnes verticales se repetent par groupe de 6
mais sont parfoix egale a 1 par multiples de 3 ou 2
les lignes horizontales se repetent par groupe de 7
une ligne sur 7 est nulle (x multiples de 7)
une ligne sur 7 est a 1
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 2 4 1 2 4 1 2 4 1 2 4
3 3 2 6 4 5 1 3 2 6 4 5
4 4 2 1 4 2 1 4 2 1 4 2
5 5 4 6 2 3 1 5 4 6 2 3
6 6 1 6 1 6 1 6 1 6 1 6
7 0 0 0 0 0 0 0 0 0 0 0
On constante ici que la deuxieme moitie des lignes ce deduit des premieres
en effet 6 % 7 c'est aussi -1 % 7
donc 6 quand on le multilis par lui meme donne une suite de 6 1 6 1 6 1
c'est a dire -1 +1 -1 +1 -1 +1 ....
de meme pour 5 qui est auusi -2 % 7
donc pour ecrire la ligne 5 il suffit de recopier la 2
en rajoutant un signe moins (le complement a 7)
sur toutes les puissances impaires :
4 c'est aussi -3 % 7 ....
de plus la ligne 4 ce deduit de la 2 en sautant un element sur deux
la ligne 6 est aussi le produit des termes de lignes 2 et 3 ( %7)
Bref : il ne reste environ que la motie des lignes premieres !!!
et on constante que tous les (X^6)%7 sont egal a 1 (element neutre)
---
soit les memes valeurs lues en modulo 9 = 3 * 3
(phi = 6 = 2 * 3 ) != phi(3) * phi(3) = 2 * 2
les colonnes verticales se repetent par groupe de 6 ( pas de 3 ou 9 ou 2)
(si on exclus les x multiples de 3)
les lignes horizontales se repetent par groupe de 9
une ligne sur 3 est nulle
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 2 4 8 7 5 1 2 4 8 7 5
3 3 0 0 0 0 0 0 0 0 0 0
4 4 7 1 4 7 1 4 7 1 4 7
5 5 7 8 4 2 1 5 7 8 4 2
6 6 0 0 0 0 0 0 0 0 0 0
7 7 4 1 7 4 1 7 4 1 7 4
8 8 1 8 1 8 1 8 1 8 1 8
9 0 0 0 0 0 0 0 0 0 0 0
---
soit les memes valeurs lues en modulo 15 = 3 * 5 (phi = 8 = 2 * 2 * 2)
les colonnes verticales se repetent par groupe de 8 ( 4 ?)
mais sont parfopis egale a 1 par multpiles de 2
les lignes horizontales se repetent par groupe de 15
une ligne sur 15 est nulle (x multiples de 15)
une ligne sur 15 est a 1
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 2 4 8 1 2 4 8 1 2 4 8
3 3 9 12 6 3 9 12 6 3 9 12
4 4 1 4 1 4 1 4 1 4 1 4
5 5 10 5 10 5 10 5 10 5 10 5
6 6 6 6 6 6 6 6 6 6 6 6
7 7 4 13 1 7 4 13 1 7 4 13
8 8 4 2 1 8 4 2 1 8 4 2
9 9 6 9 6 9 6 9 6 9 6 9
10 10 10 10 10 10 10 10 10 10 10 10
11 11 1 11 1 11 1 11 1 11 1 11
12 12 9 3 6 12 9 3 6 12 9 3
la aussi on vois que les lignes 1 et 4
sont liees en complement a 5 et alternees
de meme les lignes 7 et 8 sont liees en complement a 15 et alternees
les lignes 6 et 9 sont liees en complement a 15 et alternees
les lignes 5 et 10 sont liees en complement a 15 et alternees
les lignes 4 et 11 sont liees en complement a 15 et alternees
les lignes 3 et 12 sont liees en complement a 15 et alternees ...
---
soit les memes valeurs lues en modulo 35 = 7 * 5 (phi = 24 = 2 * 2 * 2 * 3)
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 2 4 8 16 32 29 23 11 22 9 18
3 3 9 27 11 33 29 17 16 13 4 12
4 4 16 29 11 9 1 4 16 29 11 9
5 5 25 20 30 10 15 5 25 20 30 10
6 6 1 6 1 6 1 6 1 6 1 6
7 7 14 28 21 7 14 28 21 7 14 28
la ligne 6 ce deduit de la 3 et de la 2 !
Comme tous X peut etre decompose en facteur premier
on peut se contempter de garder que les lignes
correspondant a des nombre premier 1 2 3 5 7 11
la multiplication etant associative on peut reconstituer
les autres lignes .
---
synthese
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1
2 4 8 16 32 64 128 256 512 1024 2048
%2 0 0 0 0 0 0 0 0 0 0 0
%3 2 1 2 1 2 1 2 1 2 1 2
%4 2 0 0 0 0 0 0 0 0 0 0
%5 2 4 3 1 2 4 3 1 2 4 3
%6 2 4 2 4 2 4 2 4 2 4 2
%7 2 4 1 2 4 1 2 4 1 2 4
3 9 27 81 243 729 2187 6561 19683 59049 177147
%2 1 1 1 1 1 1 1 1 1 1 1
%3 0 0 0 0 0 0 0 0 0 0 0
%4 3 1 3 1 3 1 3 1 3 1 3
%5 3 4 2 1 3 4 2 1 3 4 2
%6 3 3 3 3 3 3 3 3 3 3 3
%7 3 2 6 4 5 1 3 2 6 4 5
4 16 64 256 1024 4096 16384 65536 262144 1048576 4194304
%2 0 0 0 0 0 0 0 0 0 0 0
%3 1 1 1 1 1 1 1 1 1 1 1
%4 0 0 0 0 0 0 0 0 0 0 0
%5 4 1 4 1 4 1 4 1 4 1 4
%6 4 4 4 4 4 4 4 4 4 4 4
%7 4 2 1 4 2 1 4 2 1 4 2
5 25 125 625 3125 15625 78125 390625 1953125 9765625 48828125
%2 1 1 1 1 1 1 1 1 1 1 1
%3 2 1 2 1 2 1 2 1 2 1 2
%4 1 1 1 1 1 1 1 1 1 1 1
%5 0 0 0 0 0 0 0 0 0 0 0
%6 5 1 5 1 5 1 5 1 5 1 5
%7 5 4 6 2 3 1 5 4 6 2 3
6 36 216 1296 7776 46656 279936 1679616 10077696 60466176 36279056
%2 0 0 0 0 0 0 0 0 0 0 0
%3 0 0 0 0 0 0 0 0 0 0 0
%4 2 0 0 0 0 0 0 0 0 0 0
%5 1 1 1 1 1 1 1 1 1 1 1
%6 0 0 0 0 0 0 0 0 0 0 0
%7 6 1 6 1 6 1 6 1 6 1 6
7 49 343 2401 16807 117649 823543 5764801 40353607 282475249 1977326743
%2 1 1 1 1 1 1 1 1 1 1 1
%3 1 1 1 1 1 1 1 1 1 1 1
%4 3 1 3 1 3 1 3 1 3 1 3
%5 2 4 3 1 2 4 3 1 2 4 3
%6 1 1 1 1 1 1 1 1 1 1 1
%7 0 0 0 0 0 0 0 0 0 0 0
Rq : En utlisant le theoreme des restes chinois on fini par decouvrir X !!!
EN COURS DE REDACTION !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
DEFINITIONS
* NOMBRES PREMIERS ENTRE EUX (relativ prim) :
deux nombres sont premiers entre eux si n'on aucun diviseur commun
(autre que 1)
ex :
5 et 6 sont premier entre eux !
( leurs plus petit commun multiple PPCM est egal a leur produit 30)
( leurs plus grand commun diviseur PGCD est 1)
10 et 6 ne sont pas premier entre eux
on peut les diviser chaqun par 2
( leurs plus grand commun diviseur PGCD est 2)
et leur PPCM est 30 (est pas 60)
( 10 * 6 = pgcd *ppcm )
Un nombre premier en absolu
ne peut pas se decomposer en produit de plusieurs nombres
( il est donc premier relatif avec tous les autres )
un nombre en general est le produit (la factorisation)
de un ou plusieurs nombres premiers
par exemple 9 est egal a 3 * 3
par exemple 63 est egal a 3 * 3 * 7
on a en general
A * B = PGCD(A,B) * PPCM(A,B)
* POLYNOME DE NEWTON, TRIANGLE DE PASCAL, COMBINAISONS
Polynome de Newton (A+B)^P
(A+B)^2 = A^2 + 2 * A * B + B^2
(A+B)^3 = A^3 + 3 * A^2 * B + 3 * A * B^2 + B^3
(A+B)^4 = A^4 + 4 * A^3 * B + 6 * A^2 * B^2 + 4 * A^3 * B + B^4
les coefficiant entiers des termes multpilicatif sont C(N,P) :
Donnes dans le triangle de pascal :
C(N,P) 0 1 2 3 4 5 6 7 8 9 10 N
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
9 1 9 36 84 126 126 84 36 9 1
10 1 10 45 120 210 252 210 120 45 10 1
11 1 11 55 165 330 462 462 330 165 55 11 1
12 1 12 66 220 495 792 924 792 495 220 66 12 1
13 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
P N inf ou egal a P
RQ lignes avec un P premiers
1, 3, 5, 7, 11 ...
ne contiennent qu es multipes de P
ou des 1 ( au deux extremitees )
Si le nombre est nom premier, comme par exemple 6 = 2 * 3
on a des coef egaux a 1 , et des multiples de 3 , de 5 , de 4 ...
ON reporte la demonstration juste apres,
la definition et le calcul des combinaisons .
Combinaisons :
Comment choisir 2 fois A dans (A+B)(A+B)(A+B)(A+B)
je peut choisir le premier A dans un des 4 termes
le deuxieme A dans les 3 termes restant soit 4*3 arragement;
( ensuite je choisi 2 foix B )
A * A * B * B
A * B * A * B
A * B * B * A
B * A * A * B
B * A * B * A
A * A * B * B !
B * B * A * A
A * B * A * B !
B * A * A * B !
A * B * B * A !
B * A * B * A !
B * B * A * A !
Mais peut importe l'ordre que le premier A soit dans le 1 terme
et le deuxieme soit dans le 3 eme terme
ou que le premier soit le 3 eme et les segond dans le premier ;
C'est pareil
on va tous diviser par 2
C(2,4) = 4*3 / 2 = 6
C(N,P) comment choisir N elements dans une liste de P elements
sans tenire compte de l'ordre :
C(N,P) = P * (P-1) * (P-2 ) ... / P * (P-1) * (P-2) ...
soit en utilsant le symbole ! factorielle :
C(N,P) = P ! / ( (P-N) ! * N ! )
on retrouve tous les coefficiant du triangle de Pascal
dans le polynome de Newton :
symetrie :
C(P-N,P) = C(N,P) ; (choisir N terme c'est comme en elliminer P-N )
extrmitees :
C(0,P) = 1 C(M,P) = 1;
calculs :
C(N+1,P+1) = C(N,P) + C(N,P+1)
Dans le triangle de Pascal un nombre est la somme des deux nombres
qui le precede et du meme rang, sur la ligne precedante !
et on peut ecrire le polynome
(A+B)^P = C(0,P) * B^P
+ C(1,P) * A^1 * B^(P-1)
+ C(2,P) * A^2 * B^(P-2)
+ C(3,P) * A^3 * B^(P-3)
+ ....
+ C(P,P) * A^P
* INDICATEURT EULER ( ex pour N = 63 = 3 * 3 * 7)
Combien un Nombre N a il de nombre inferieur ou egal a lui meme ( ici 63)
et premier avec lui ?
A priori, pas plus de N ( ici 63 )(en comptant aussi 1 et 63 ) !
mais on doit enlever tous les mutiples de 3 : 3 6 9
donc il en reste 2/3 de 63
idem pour les multiples de 7
il en reste donc 6/7 ...
soit donc 63 * 2/3 * 6/7 = 3 * 3 * 7 * 2/3 * 6/7 = 3 * 2 * 6 = 36
PHI(63)=36
Ce nombre est indicateur Euler PHI utilise precedament qui denombre
l'ensemble des nombres I non elimines, qui verifis donc pgcd(I,63) = 1
(il reste : 1 2 4 5 8 10 11 13 16 17 19 20 ..... 62.)
On connais donc leur nombre sans les connaitres individuellement !
Dans le cas general Pour N= p1^A * p2^B * p3^C ....
( p1 p2 p3 etant les nombres premiers de factorisation de N )
on trouve PHI(N) = N * (1 - 1/p1) * (1 - 1/p2) * (1 - 1/p3) ....
Dans le cas ou N est le produit de
Deux nombres premiers differents p1 et p2
PHI(n=p1*p2) = (p1-1) * (p2-1)
( par definition PHI(1) = 1)
* Ordre_multiplicatif_M( A ) : C'est le plus petit entier K
tel que (A^K) %M = 1 ( pour A non null )
on a vus precedament que ce nombre ne peut pas depasser M-1
du fait que les restes d'une division modulo M sont limite a M-1
* associativite commutativite des operateur %
A priory X ^P % M = ( X % M) ^ P % M = .
et on peut faire la calcul dans ordre que l'on veut
et parfois la notation %m (deviends sous entendu ou optionnelle)
certain mathematicien utilise de preferance operateur d'egalite modulo
note par trois trait horizontal (non disponible en ASCII de base ) !
exemple 5 "est egal a" 11 (en modulo 3 )
puisque ils sont egaux leur differances 11 - 5 = 6 est donc nulle !
(ce qui est vrai : 6 en modulo 3 est bien nul )
Bref on doit faire tres attention de quoi on parle
pour ce debaraser de ces anbiguites et eviter la notation modulo
on peut transformerr la notation A % M = H en A = H + K * M
avec des entier relatif
Mais il y des contraintes ou des simplifications
si pendant les calculs on tombe sur
le 0 zero ou le 1 (l'ellement neutre de la multiplication)
on peut trouver le resultat tres rapidement ! .....
THEOREME FERMAT
si x==0 alors X^? est null
si x est non nul et pour peut que M soit premier :
alors on a :
X^M % M = X % M ( en fait il sagit de egalite modulo M )
* Soit la forme generale suivante du theoreme
X^M - X = K * M qq soit X
pour peut que M soit premier !
( RQ on peut demontre le petit th de Fermat
par recurance X X+1 .....
avec le developpemnt du polynome de newton (X+1)^M
donc les coefficiant,
qui sont dans le triangle de Pascal CiM,
sont tous des multiples de M
(sauf le premier et le dernier qui sont egaux a 1 :
C(N,M) est un nombre entier de conbinaisons,
c'est la maniere de choisir N (facteur X)
dans les M termes du polynome
(X+1) (X+1) (X+1) ...
on a la choix entre X ou 1 a chaqun des M termes
( N inferieur ou egal a M)
C(3,M) = M * (M-1) * (M-3) / 1 * 2 * 3
( le nombre de combinaison non ordonees
= arrangement / permutatations )
C(i,M) = M! / (M-i)! / i!
le nombre M ce trouve au numerateur
et pas au diviseur
( sauf C(0,M) et C(M,M) qui sont egaux a 1)
C(3,7) = 7 * 6 * 5 / 1 * 2 * 3 = 5 * 7
Si M est premier il n'a pas de diviseur au denominateur
(ni ailleurs de par definition)
Dans ce cas la C(i,M) est :
soit 1 soit un multiple de M ,
car c'est un entier et que M est premier
Donc si X^M % M = X (X inferieur a M)
supposont que X^M - X = K * M
alors
((X+1)^M = X^M + M * (.... ) + 1
on remplace X^M par ca valeur pecedante X + K * M
on a (X+1)^M = 1 + X + K * M + M * (.... )
avec Y = X+1
on a la memem forme Y^M = Y + Z * M
Donc si la relation est vrai pour X=1
elle est vrai aussi pour tous X+1
Pour X=1 c'est vrai ( 1 % M = 1 )
donc ....c'est vrai quel que soit X !
pour M premier
On demontre bien alors que
X^M - X = K * M qq soit X
pour peut que M soit premier !
RQ si M est premier alors M = 1 + PHI(M)
Pour faire la demonstrations
par recursion du theoreme de Pascal :
M doit etre premier !
Plusieur autre demonstrations par recurance peuvent etre abordees
par cette methode ....
* On peut vouloir etendre et generaliser ce theoreme
a un nombre non premier !
par exemple produit de
deux nombres premiers M = P1 * P2 (differants)
On se rends compte que cette approche directe ne marche pas
car il y a des C(i,M)
qui ne sont pas multiples de M (ou egal 1)
Pour peut que i soit un multiple uniquement d'un seul
des composants P1 ou de P2 et pas de l'autre
Car ils vont etre divises par un des termes P1 ou P2 ;
mais pas par l'autre (puisque P1 et P2 sont differants)
(ces termes ne sont plus egaux a 0 en modulo M)
(evidament C(0,M) et C(M,M) reste egal a 1)
un exemple avec M = 3 * 5 :
C(3,15) = 15 * 14 * 13 / 3 * 2 *1
= 455 = 30 * 15 + 5 ;
C(3,15) % 15 = 5
C(12,15)= 5
C(6,15) = 15 * 14 * 13 * 12 * 11 * 10 / 6 * 5 * 4* 3 *2
= 5005 = 333 * 15 + 10 ;
C(6,15) % 15 = 10
C(9,15) = 10
C(5,15) = 15! / 10! / 5! = 3003 = 200 * 15 + 3;
C(5,15) % 15 = 3
C(10,15)= 3
? ? ?
VARIANTE TH FERMAT
On peut ecrire le Th de fermat sous une autre forme
pour essayer de resoudre le probleme
( par un petit coup de marche arriere )
(en divisent tous par X ( c'est la division % M premier))
(X^(m-1)) % M = 1 ( si x est NON NULL % M !!!)
Cette variante du TH de Fermat est moins generale
car pour diviser par X il est necessaire
que X%M soit different de zero
soit PGCD(X,M) == 1
X^(M-1) = 1 + Q * M
si PGCD(X,M) == 1 et M premier
X^(M-1) % M == 1
RQ si X= K*P1 ou X=L*P2 cela ne marche pas !!!!
Mais elle a l'avantage de se generaliser dans
le cas ou M est le produit de deux nombre premiers differents
P1 et P2
sous la forme (X^((P1 - 1) * (P2 - 1)) = 1 + S * (P1 * P2)
Il suffit de develloper le calcul
S = X^((P1-1)*(P2-1)
= (X^(P1-1))^(P2-1) = (X^(P2-1))^(P1-1)
en utilisant deux fois le theoreme precedant de Pascal,
que l'on peut toujours utiliser
vus que P1 est suppose etre premier
vus que P2 est suppose etre premier
X^P1 = X + K * P1
X^P2 = X + L * P2
si X % P1 != 0 et X % P2 != 0
(pour eviter des multiplication par zero)
alors
X^(P1-1) est de la forme
1+ K/X * P1 = un entier non nul = 1 + V * P1
X^(P2-1) est de la forme
1+ L/X * P2 = un entier non nul = 1 + W * P2
donc
S = (X^(P1-1) ) ^(P2-1) est de la forme 1+ W * P2
par symetrie
S = (X^(P2-1) ) ^(P1-1) est de la forme 1+ V * P1
on en deduit que K * P2 = L * P1
et commme P1 est different de P2
P2 ne divise pas P1 donc il divise L
autrement dit S = 1 + R * P1 * P2
Donc ( X^((P1-1)*(P2-1) ) % M = 1
pour peut que X % P1 != 0 et X % P2 != 0
avec P1 et P2 des nombres premiers differants
RQ : si X= K*P1 ou X=L*P2 cela ne marche pas !!!!
On peut genaraliser a M = P1 * P2 * P3 ...
ou P1 P2 P3 sont des nombres premiers tous differants
ON peut alors verifier aussi (X ^ PHI[M)) % M = 1
si PGCD(X,M) == 1
RQ : si X= K*P1 ou X=L*P2 cela ne marche pas !!!!
on ne trouve pas 1 : mais K un inverse de X en modulo M
K*X % M == 1
Ce qui donne bien au rang suivant la forme classique
du th de Fermat
X ^( 1 + Z * PHI(M)) % M = X % M
dans le cadre du RSA le filtre PHI(M)
est simplement (P1 -1) * (P2 -1) * ....
Ordre multiplicatif de X tel que PGCD(X,M) == 1
est egal a PHI(M)
PGCD(X,M) == 1 est la pour eviter les ZERO !
Elliminer les 1 :
Comment etre Franc et eviter les Un
soit X^K == 1 + S * M (ceci est possible si PGCD(X,M) != 0)
ceci est possible si P est egal a (P1- 1) ou (P2 -1)
ceci est possible si PGCD(P,PHI(M)) != 1
Pour eviter avoir X^K %M == 1
il est preferable que PGCD(P,PHI(M)) == 1
il est preferable que P soit premeir !
OPTIMISATION DES CALCULS
RQ A%(m1*M2) % M2 = A % M2 : operateur % modulo est distributif
Exemple je veux calculer X^17 :
* La methode bete : X2 = X * X X3 = X2 * X .... 17 multiplications
* Plus evolue : j'ecrit 17 en base 2 : 10001 = 2^4 + 1
je calcule la suite
X2 = X * X ; X4= X2 *X2; X8 = X4 * X4; X16 = X8 * X8;
en 4 multiplication j'ai reconstitue la base
et j'ai plus qu'a multiplie entre eux
ce qui sont marque par des 1 binaires :
X17 = X16 * X (5 multiplication en tout)
( RQ dans ces calculs suivant je ne precisse plus % M , ce n est pas utile,,
car A %( F * H) = A %H = A %H %H %H ... !)
RQ ici pour obtimiser les calculs
on a utilise une decomposition en binaire
parce que les utilisateurs et les ordinteurs
sont habitues a ca !
Mais on pourrais faire ces calculs dans
n'importe quelle base ou representation numerique !
* Mais il y a beaucoup de variantes pour optimiser les calculs
Exemplez X^161 (10100001)
ce truc la vas couter a priory 7+2 soit 9 multiplications !
mais je peut aussi ecrire 161 = 23 * 7 = 7 * 23
(x^7)^23= X^161
codage 7 (111)
X2 = X * X ; X4 = X2 * X2; ... ; Y = X4 *X2 * X ;
total 4 multiplications
decodage 23 (10111)
Y2 = Y * Y ; Y4= Y2 * Y2 ; Y8 = ..., Y16=
4 multiplications
Y23 = Y16 * Y4 * Y2 * Y;
3 multipliucations
total 7 multiplications (* au plus !)
(resultat Z = Y^23 = (X^7)^23 = X^161
(et si j'ai fait le calcul en modulo M
tel que 1+ K * phi(M) = 161 !!!!
alors x^161%M == X trouvez donc M !!! )
le calcul global semble plus long (11 multiplications au lieu de 9)
mais il permet en reception de calculer la valeur sans la connaitre !
Resultat en ecrivant 161 = 7 * 23 :
* on peut coder Y=X^7
et on a besoin de connaitre X pour cela !
* Mais Pour decoder Z= (Y^23) (et obtenir x^161)
ON N'A PAS BESOIN DE CONNAITRE X
(sinon c'est plus du decodage !!!);
Mais on doit etre sur que Y n'est jamais egal a 1
( pour tous X != 1 )
( sinon l'adn de X est perdu dans le pseudo codage !)
c'est pour cela que l'on verifis
que 7 est premier avec PHI !
global ((x^7)^23 ) % ...
RSA EXEMPLE NUMERIQUE
Soit donc M = 5 * 11 = 55
on a PHI(55) = 4 * 10 = 40
on verifis que avec E=7 et D=23
E*D= 161 = 1 + K * PHI = 1 + 4 * 40
Pour etre sur que E a un inverse D modulo PHI
il ne doit etre premier avec les composant de PHI
( ici 7 est un nombre premier absolu
qui verifis aussi : pgcd (7,40) = 1 ! )
Ce controle avec indicateur Euler s'assure que X^7
ne vas pas devenir element neutre 1 (en %M ) ! ( car 1 ^N = 1 )
sinon on a perdu X en codent !!!
Comme le raisonnement est symetrique
X^23 est different de 1%M (pour X >1 )
ce qui permet la signature
( qui sera decode par Y^7 la clef publique )
* RQ: quand on calcule pour le RSA
les deux nombres premiers P1 P2,
les deux nombres E D
on peut garder ces infos dans la clef privee
pour obtimiser le decodage Y^D ....
X^ 161 % 55 = X si pgcd(X,55) = 1
X^ 7 % 55 != 1 si X % M != 1
THEORME
Euler Fermat ameliore
C'est une genralisation pour M = P1 * P2,
avec P1 et P2 des premiers distincts :
(x^PHI(M) ) % M = 1 si x non null et PGCD (X,M) = 1
qui ce deduit simplement du TH de Fermat par distributivitee !
Pgcd (X,P1*P2) permet de selectionner les X qui vont bien;
en elliminent les mutiples indesirable !
( Dans le cas du RSA M= P1 * P2,
DEUX nombres premiers differents P1 et P2
Si X est non null est inferieur a P1 et P2 ca marche aussi ! )
L'ordre multiplicatif K de certain A modulo M
est au plus egal a PHI,
il peut se reduire dans certain cas X a des sous multiples de PHI
Par exemple si M est egale a 5 * 11
ordre multiplicatif pour %5 est 4 = 2 * 2
ordre multiplicatif pour %11 est 10 = 2 * 5
Par associativite on deduit que certain X^P peuvent se neutraliser
pour P multiple de 4 en %5
ou pour P multiple de 10 en %11
On en deduit que pour modulo %55
les neutralisation a 1 pourrais se produire
sur les multiples 2 et 5 ( au plus tard a 40)
Donc on choisi E ( pour coder les X ( pour Y= x^E%M ))
tel que PGCD =(E ,PHI) = 1
ce qui evite de tomber sur element neutre pour tous les Y
On choisi ensuite D tel que ED soit 1 + K * de PHI
( pour retrouver X au decodage )
Autrement dit dans le RSA on passe sont temps a eviter les zero et les un :
le X a coder doit avoir un pgcd(X,M) == 1
pour eviter que les multiplications, modulo ne devienne jammais nulle
Le Y=X^E%M doit etre different de 1
on s'assure alors que PGCD(E,PHI(M)) == 1
COEFFICIANTS DE BEZZOU
Soit deux nombre entier A et B
il existe deux entiers U et V
tel que U*A + V*B = K * PGCD(A,B)
si on rapport cela a equation de l'ordre multiplicatif
E * D = 1 + K * PHI(M)
on trouve que D est egal au coefficiant de bezzou U
de ( E,PHI )
U * E + V * PHI = PGCD(E,PHI) = 1 (si E et PHI sont premeir)
D * E = 1 - V* PHI
donc X^(E*D)%M = X
ALOGORITHME EUCLIDE
Le PGCD(A,B) plus grand commun multiples de A et de B
Si A et B sont premier entre eux alors leur PDGCD(A,B) est egal a 1
et reciproquement
On peut calculre le PGCD par recurance
PGCD(A,B) = PGCD(B, A%B)
pseudo code
avec A>B
while(B) do
NB = A % B
A = B
B = NB
done
return(A)
On sait qu'il existe U et V les coef de Bezzou tel que
U * A + V * B = PGCD(A,B)
On peut calculer ces coefficient en meme temps que le pgcd
par algorithme Euclide etendu
pseudo code
avec A>B
U = 1 V = 0 ( A0 = 1 * A0 + 0 * B0) les deux vecteurs
UU = 0 VV = 1 ( B0 = 0 * A0 + 1 * B0) initiaux
while(B) do
Q = A // B division entiere ( A % B = A - Q * B )
NB = A % B
A = B
B = NB
NUU = U - Q * UU
U = UU
UU = NUU
NVV = V - Q * VV
V = VV
VV = NVV
done
return (PGCD=A , U , V)
les 3 groupes iteration ci-dessus A B U UU V VV
sont similaires et peuvent etre traites simultanement
par un notation vectorielle
on utilise deux vecteurs que l'on combine lineairement
pour obtenir un troiseme (qui est le reste de la division A % B ) ,
on recommence a iterrer sur le 2 eme et le 3 eme ...
A=A0 U=1 V=0
B=B0 UU=0 VV=1
while(B) do
Q= A//B
(NB NUU NVV) = ( A U V ) - Q * ( B UU VV)
(A U V) = ( B UU VV)
(B UU VV) = (NB NUU NVV)
done
return (PGCD=A , U , V)
PGCD(A0,B0) = U * A0 + V * B0
TESTS DE PRIMALITEE
IL est necesaire dans les calculs RSA
de trouver deux nombres premier P1 et P2 differants et tres grand !
Ce qui permet de valider les algorithme de Fermat ....
Ceci peut etre long et doit donner des resultats variees
(non predictibles) et on n'a pas pour le momemnt
algorithme rapide et sur (heureusement *) :
On n'est pas sur en fait que les nombres trouve
son vraiment premiers :
Il existe des nombres dit de Kermichel
qui peuvent etre utilise dans le RSA
sans etre premier !
M pourrais etre alors le produit de trois nombres premiers differents
Dans le cadre du RSA on prends le probleme a l'envers
on verifis que les nombres trouves pour le moment
fonctionnent en testant un cycle cryptant decryptant
sur des valeur de X de test special
les nombres premier 1 3 5 7 11...
et puis c'est tous !!!
Si ca plante on continus a chercher d'autres nombres premiers
compatible RSA ....
Si ca ne plante pas on espere alors que cela va marcher !
(* En matier de securitee cryptage :
le mieux peut etre ennemis du bien !)
RESUME RSA
On sait que les puissances sucessives de X
finissent par redonner X ( en modulo M )
au bout d'un certains temps !
M est a priori le produit de deux nombres premiers differants P1 et P2
on calcule sonnt indicateur Euler PHI= (P1 - 1) * (P2 - 1)
Y= (x^E) % M cryptage
Z= (y^D) % M decryptage
on veut que Z soit egal a X
au minimum on doit avoir (X ^(E*D) ) % M egal X % M
Ceci est vrai avec th Euler Fermat si (E*D) = 1 + K * PHI(M)
( E et D sont des genres d'inverses modulo PHI )
Mais cela n'est pas suffisant ;
Il est necessaire en plus que Y ne soit pas egal a 1
( car sinon on perd x )
Pour eviter cela, E doit etre premier
avec tous les composant de PHI(M) !
Traditionellement on prends E de la forme 2^K+1
3 5 32767 .....
qui sont aussi des nombres premier dans absolu
(donc ils ne sont pas des diviseur de PHI )
Il reste a calculer D l'inverse de E modulo phi(M) !!!!
si pgcd (E,PHI) = 1 alors D existe, pour le trouver,
on utilise le TH Euclide etendu ( calcul pgcd et des coef Bezzou)
Par iterations on trouve D , N , PGCD (algo euclide etendu)
pour N * PHI + D * E = pgcd(PHI,E) = 1
( pgcd = 1 par choix de E premier )
Algo Euclide etendu permet de trouver D ( le coef Bezzou V )
et verifis que le PGCD est bien 1 ( D et E sont alors premiers avec PHI )
La celf publique se resume a M et a E !
tous le reste n'est connus que dans la clef prive !!!
LIMITES DU CRYPTAGE RSA
* 0 est toujours code 0
* 1 est toujours code 1
* si on code un X trop grand superieur a M
apres decodage on ne retrouvera pas le meme
mais plutot son equivalant X % M
si par Hazard X=P1 ( ou P2) il sera code O,
il faudrai que X soit plus petit que P1 et P2
( que l'on peut extimer a racine carre de M )
et garder un peut de place pour faire les calculs
* limiter la taille du X a coder
typiquement pour une clef de 1024 (128 octets) bits
on peut se limites a 880 bits (110 octets)
* inversement si le nombre a coder X est
trop petit il est transmis sans etre 'crypte'
La norme 509 prevois :
Que l'on utilise pour exposant public un nombre
premier de la forme 2^? + 1 :
3, 5, 2^16 + 1 = 65537 ....
Si le nombre a coder n'a pas suffisament de bits significatif
( LB2 (X) est le log base 2 de x )
compare a la taille de la clef ( son modulo M ) :
Donc si LB2(X) * 16 est inferieur a LB2(M)
Alors le 'crypage' peut se faire
sans avoir a utiliser le %M
( donc independament de la clef privee utilisee)
il se reduit a X^65537
De fait on peut decrypter :
avec n'importe quelle autre clef
de taille superieur ( avec un M plus grand )!
Il suffit alors de recrypter le nombre obtenue
avec la premiere clef publique initiale
et de comparer les resultats pour verifier !!!
En premiere approximations :
pour une clef de 1024 bit le nombre a coder doit avoir
au moins 64 bits significatif (8 octes) (1024/16)
pour une clef de 2048 bit le nombre a coder doit avoir
au moins 128 bits significatif (16 octes) (2048/16)
RQ : une signature MD5 utilisee
juste 16 octets (un peut plus en SHA !)
donc pour instant signer du MD5 avec une clef de 2048 bits
est faisable (mais oublier MD5 pour une clef plus grande !)
|