Saturday, 7 March 2009

Cifrado RSA

Últimamente estoy bastante metido con el tema de los cifrados y la verdad es que me encantan, y hace poco tiempo descubrí este cifrado (RSA) y después de crear varias aplicaciones, voy a explicar mis impresiones y su funcionamiento. El sistema criptográfico con clave pública RSA es un algoritmo asimétrico cifrador de bloques, que utiliza una clave pública, la cual se distribuye (en forma autenticada preferentemente), y otra privada, la cual es guardada en secreto por su propietario. Los mensajes enviados usando el algoritmo RSA se representan mediante números y el funcionamiento se basa en el producto de dos números primos grandes (mayores que 10100) elegidos al azar para conformar la clave de descifrado. Su nombre viene de Rivest, Shamir, Adelman que fueron las 3 personas que lo desarrollaron. Se utiliza como certificado digital para el uso de transmisiones seguras por SSL.

Su implementación es bastante sencilla hablando en términos matemáticos, pero ya os digo que hay que tener una buena base para poder trabajar con el.

  • ¿Cómo funciona?...
Este ejemplo lo he sacado de la universidad de Virginia del departamento de Informática:

Montaje:
  1. Roberto escoge 2 números primos secretos, los llamaremos p y q. Para estar seguros, los números deben ser de al menos 100 dígitos decimales.
  2. Roberto calcula n = p * q.
  3. Roberto encuentra un número donde el máximo común divisor de e y (p - 1) * (q - 1) = 1.
  4. Roberto encuentra un número d donde d * e = 1 mod ((p - 1) * (q - 1)).
  5. Roberto publica n y e como la llave pública. Guarda d en secreto y destruye p y q.
Encriptación: TextoCifrado = Me mod n
Desencriptación: Mensaje = Cd mod n

Parece sencillo, no??, pues no!. Ya que computacionalmente es muy difícil trabajar con números tan grandes. Por ejemplo aquí os dejo una muestra de lo que seria el número p:

113597550342913139484582617710485393473499376727618391328445984935106691
3
69028893330897476831258049610918235692377185897359989517386645943094695
1
50977695887676958666950187986111126533228991356398940379429511249627604
3
40534511948163422336817523503988511092489662939475076676115936360595746
710728564766446987589

Este número con más de 300 dígitos que además es primo, es intratable matemáticamente, y aquí es donde nos tenemos que estrujar el cerebro creando aplicaciones y algoritmos capaces de tratar estos números tan grandes. Además, este no es el resultado, solo es uno de los números, luego hay que hacer todas las operaciones p * q, etc, y al final obtienes una cadena de números que puede ser que tengas más de 1000 dígitos. Imaginaros que incluso hay competiciones para resolver cifrados RSA, donde si resuelves el RSA-2048 te dan 200.000 $ (vaya tela, no?). Lo cierto es que es casi imposible romperlo, sobretodo porque computacionalmente su resolución costaría miles de años. Su dificultad radica en la factorización de los números, ya que a partir de n, debemos calcular los números primos p y q que generaron la expresión. La mayoría de los RSA sencillos los consiguió resolver Lenstra con su algoritmo de factorización elíptica (ya explicaré un poco más con detalle su algoritmo para la resolución de factorización de números).

Por ejemplo, un cifrado creado con mi aplicación seria (creado en java con RSA 512 con un tamaño de clave de 1024):

1. Creo p y q aleatoriamente, y los expreso en Hexadecimal para que no ocupen tanto:

p:
A0B5237F7C9B03F7795C1DDFECE885A869E7855864D621D2F88620BB6CFF00BBE2
9795818DE81F0A5E3C5ABDD04264AD0EC396274363DD06387F78BA86BFBC01F974
E1CB682E5A538D2DBCE71CE41403E87A14D797B370492FB72F39069BFFF7D17325
D08C1765B5536562539FBC14A60DF47CBAC225E4316307D8316D1D3A43

q:
C158BA734CD6D27243B27A6184AA1C92CDF253D5861A961FB233B1B0B4A6B3D08C
C4996976C4981BAD79CDFE6C1A6F3C08637D440421A445BC991F722C0CF223F26F
223BF15604ECAD4DF5514A78A53EB5B6D74661C029E7CCA869511630E547C886DC
D499D847FD506C5EEC3E07F90943DF70E108C2CE7317AF518A74F3A9DB


2. Luego calculo n y genero e dinámicamente cumpliendo las condiciones anteriormente dichas:

Clave publica (n,d)
n:
796043134E29E82661ECC5588EF107153B3063E82B017CDFC066E131B4AB41713F
48BC9
831E8C05F990D582D8B181042C1CD8BC45026955FA4647545F2749530BCD3
8F075E9685C
05A0E63FD341A08BCA9BC38AA07E90F3E0488AD29380AB04585EF30
B92904371B7F1B1D02D26E6EBABB02CA04847B02EEEBE2B655D5049B39A1231672
B3B818F1F3716DF1879621664F3294CCC03596410589ED0A0992EAD927D513676C
F4EA9639B588A0EF722948AB484C21F24CF9210920810577A520F94AA0735B51B0
39B71E1FA164B0CE1D82050ED8E4BA2C4D958D237DF686F24AED775439F14E6E4B
D542E480CC91A0DC2E95EC7FE7F5D1DA836BC7FF934D101251


e:
3B725B2D46528D708FC35B302F83368DBC4EB0A7ED8BD858486070ED5B39D401E8
F3C7CA62D3CD7AAA46C4CCE0242537B7746DD249B64BED807F4D68D039195A99E7
4BED1E793170961D5E29D7E787429A7F4ADC89235C6A7EF5E5FBB170F531C0932E
C3F67D77D9908DB14ADBB1B281B7384CE565D4682E328A59378D55C355AF50745A
7E922297581A0662E69E41C08535D921E70C0D8C4E285EB56945B66820619138DA
0B22BDB5523232A7134EE71DB8F101F1EA9DA6CAF1EF903E3D3EACAE5A6FC74462
0230EEACE82C01A043CBBF1F53E6B54C541F61643F43786438195A1E875989FF3E
CF517313558AB17E294BE9683F3B075D3E138E8FEE7867B649

3. Encuentro el número d cumpliendo la condición anterior:

d:
8A1DDC282AB359646398026521424D4FD6627DA393FBFC4030DFD59DF361FF9B11
76C45ED150A4CAB2D28EEFF1A21558AEF8B3DABC302B4AA274B868895CBCDB7908
E558C14E2AB3AD2EB47DC7DB8E2FFB3D1A68014BD283BFBB5A863442B2F5A5B7D1
403E8C24C705085163544F5C5D629FBE9BBF6FEE0CC03F5838CF006AC770FFAD48
7D2EDB9E98B86AEFEACECB706C0CEA87AE7DF22273B95EC9DEEC268A870BB39AE7
7CBFA601D53E271D614C2D3B8EBD26C07C420A3B62E80AE397D33111816C14332A
A27B2835F74BB93DB0C0B3DADA03BC12245A51A1187FF145E34774A42D049B4914
79C4C9697797352DD0D764326FC93BB5C6459D29AE81344A9


4. Encripto un texto de prueba con el algoritmo, el resultado será la codificación en RSA:

Texto a encriptar: esto es una prueba

Texto encriptado:
240AD6B8F17E4E36049F09AFEF03C13B559453EF6EEED39D4B56DE64F2217919485
6E26FD29D1FDFC3441E2562633795A0BC124F12500E524E51983F2EABEE535E9BE0
08FBA212EAB504942E64DD819A3A6FB65C4E3294F664AC9ECA55BB166D67D435376
0F31F7B3CB27C5A642731710EC9C4F7D4664E7319E5DDFC656E312E1FB40BB5F5BB
43D93178EAEEF743A24A2A7922B8B53006ECE40D957EF2C76D13A6C7294E0AB8CB1
EEC3AEE3FE935D224528F46CD152926ABC9F0AFA70F6253F315EA302EB27FCF7E38
7AD41A3517127A342356684EA3239626EDA1A7015F29420CAB60B279A9806A3D7AC
4099ACA442D0F39ABE71B9F705F98348CD7E61893BF
35B0AB770D97B8231CEBDF7E
82EB59D98117EFAB3BAAE5433B48BD044292560B70C942C53C610147DDE98A76340
B1B84099F8946CB270FD93268C30A4F918B1A2384CF05A44F700C1A26A453F1C544
1470C1EA49DE02D2D79388CBD3A5502BAC33D5695BAFFEBA6EF4352954B5F07AE68
77E7109227D0F6E89F40A96261A9F170041CA00779853637710A36AE3C19BC37370
770EB68D7EA27B4D8E3740180CF31A76E213FB00E183EC9ACE01A47EF4797AAD84F
EEB5AE9AD7906FC4800DEBEEDEB047037F40305FCC6F586ED459B7A1BDEAC080B9D
4460F34E701BBA31C2CFBA7F063A504F0472CA382E7ABBFC7C7CB38E4C7764AA3DF
BD631CD3C3031BEBCDD
78A616AEAB961AAAF6982E11319C8087BD60770D8A65F4E2
8F11E3E0FAF0D77238CA16F38AE27AF6DDD0750349A8442C0D927A61C52431AC302
2AB5E5B44EA2BC96060CF83D8B806D3AAF025D19BF83D00F2F38970B4940A1BC998
D59AA504AC614DF452762A757E7B6E2FDAD26E032CE63928D9BD5D7E65DC0020738
F45FC6974058F6E5F5FC03B730F19825B545A5EA2548D152829EF7C4C1A5F68BD7C
6ACDD81C8673E5850130EAECABD2C22798541848BF318EFF14A677F7B752E394EEA
0A81FFC3910848F71F86DD16A868C20E5A9AE0089A1E7B65362FB882E16E2BCD285
2DC944C8E209085B019062E9A111FFEA6A637623D98BE2C814E4DCCD786605
6BE11
C73A10CC50B01F984E8226E669342217F00821AA847EE9368283B7D376FE0395D67
A3F3F29A2A234E42B827CCF834843C45FD01B4222F7DE6E86C271316F8AC46BCE06
A6279396C876B969FBE754065DAC237149B1192048170FCAE69229C1DEAE2718917
19D6092670F91A36066ABA307BE34DFEE6890A3F85707D4F55F37E6393DFF3E44C4
B9C69C168F584DD6853FBBB4FE25B512884AF695A2A31C69CC5D7071A9C237C9AEE
16FF5802BC360934B38DC95EB9E6CBF3EB27C9D871C70CDDC4689B2CB941D5ACC4F
CC0C54EA93A64666BFAE9646DCDDB21B74DC1026477EF9BCDC1F4C7641C02946755
B9FD6E9072FE2603C3B119B26BA32CA6BBEAC
32D8BD35CEEDD2E2ED57CB056C3FAA
33E8408D10A4E846704FA9A7C94A09AED7183DA507CA7BC51BD8B4A5244DF82A8C0
C914CFC5B8F7D6CB8FAD49B56FED80ABBB942C23CAA4C7026CE36B32049BC2F690C
B43CCB36319DBAF686B53651747BF12A835080F1FDB1BD035D30216BFDAAF8F2994
D592A45AAB8F96474412944D663FBEF28722ECA63EE79B0E1BF854AAECBD97D9BD8
0EC47AF60575B78FB0FE3ED0FC3BA0D2D00130D2872EDBFDB4D13B8CB6E9AD2FB7F
5B665D656C42FC4FAC505795566192B894E790CC882C29D86BE54FA60F25DCA6D50
1E1DC4AFA9BDD6A73DBB0F556A14F2243CB8EEA8BE8AD800F155DB0D07151369E07
D6234498A8169
240AD6B8F17E4E36049F09AFEF03C13B559453EF6EEED39D4B56DE
64F22179194856E26FD29D1FDFC3441E2562633795A0BC124F12500E524E51983F2
EABEE535E9BE008FBA212EAB504942E64DD819A3A6FB65C4E3294F664AC9ECA55BB
166D67D4353760F31F7B3CB27C5A642731710EC9C4F7D4664E7319E5DDFC656E312
E1FB40BB5F5BB43D93178EAEEF743A24A2A7922B8B53006ECE40D957EF2C76D13A6
C7294E0AB8CB1EEC3AEE3FE935D224528F46CD152926ABC9F0AFA70F6253F315EA3
02EB27FCF7E387AD41A3517127A342356684EA3239626EDA1A7015F29420CAB60B2
79A9806A3D7AC4099ACA442D0F39ABE71B9F705F98348CD7E61893BF
35B0AB770D9
7B8231CEBDF7E82EB59D98117EFAB3BAAE5433B48BD044292560B70C942C53C6101
47DDE98A76340B1B84099F8946CB270FD93268C30A4F918B1A2384CF05A44F700C1
A26A453F1C5441470C1EA49DE02D2D79388CBD3A5502BAC33D5695BAFFEBA6EF435
2954B5F07AE6877E7109227D0F6E89F40A96261A9F170041CA00779853637710A36
AE3C19BC37370770EB68D7EA27B4D8E3740180CF31A76E213FB00E183EC9ACE01A4
7EF4797AAD84FEEB5AE9AD7906FC4800DEBEEDEB047037F40305FCC6F586ED459B7
A1BDEAC080B9D4460F34E701BBA31C2CFBA7F063A504F0472CA382E7ABBFC7C7CB3
8E4C7764AA3DFBD631CD3C3031BEBCDD
32D8BD35CEEDD2E2ED57CB056C3FAA33E84
08D10A4E846704FA9A7C94A09AED7183DA507CA7BC51BD8B4A5244DF82A8C0C914C
FC5B8F7D6CB8FAD49B56FED80ABBB942C23CAA4C7026CE36B32049BC2F690CB43CC
B36319DBAF686B53651747BF12A835080F1FDB1BD035D30216BFDAAF8F2994D592A
45AAB8F96474412944D663FBEF28722ECA63EE79B0E1BF854AAECBD97D9BD80EC47
AF60575B78FB0FE3ED0FC3BA0D2D00130D2872EDBFDB4D13B8CB6E9AD2FB7F5B665
D656C42FC4FAC505795566192B894E790CC882C29D86BE54FA60F25DCA6D501E1DC
4AFA9BDD6A73DBB0F556A14F2243CB8EEA8BE8AD800F155DB0D07151369E07D6234
498A8169
6DF7C4E0AF907147B5C118F3B36C7604EA14CD1C35604FED6EC22E0B4B7
242935EC7192C6E66017E6C29B86B55AC088779078D7999FFBE1BFC65E1C0D70614
2279E3E30686B6885A2927E64070E3C1D73CCAC29A69EFA88B954772769219F27E0
8FFB12AC936135A4BB05241619DF2E931751CBA5C7E3B85F913CA69AB37AB7EB449
BAD4F0D8F357A96F228AF6566AEE9171EA578A84D5BE09237AFB4655F7920C2446A
07AA72F442164C796D3B901E2F700DB679311F956375ABBE37AB38E0F110FA38546
B32A82B63CFEBBF36B7E1F54C33D85BD402499A5EBA6F51FCD156999CFE0F18723A
BD9BD964E31952D4067614268293F9DF01093F1D4CE4FFEBAA4
E11EA18DB7E37167
34956D46353125996085716DCFA46FAF17B2AE948CF012D98498D2D67489960A069
D34190AC77435489169E3EA5425558535BB21DE70C32C90897606EEA5A4BA01811A
ECB2C9DB691E2F3F5C66229C5888819FCB2351377F873312506F5D8231A039D5EEF
57EB3AD2F1982F008D525C8A7ED2BB37A67EBE11DEF8FAA566072DDFC2C1A2CA903
6255AC025A2F56E900FAA683D7E3767217C75A9E0A1DF3A33D3871B30D9F4FF038B
D357D2D032AB98D438BA90A01E58805E980D5931CD882D2F6FA86192FB91AE07C26
D2AFE6CDB2B31DDFDA874F2F59B857C10929AF2BF57905D0D00D864FF0C8425748A
7E65467BAC2A64D7D24B79C067
691F272972B720F9F15B77E51085D30E422DE770B
39FD46C999222D337B54DC9201CE2A09E83046866F3F61989363B22769C62D9ED01
6A3D5869F459932A3428F2CD9A949BB40D8FF9205E3460E051811786439CFDA2867
D8DC76030DB625D8773342A0F9367E14AFFCFC466748289202663B70B473F635DBD
89964F2DE95CA0F48BF5E13369D7B440C8C2430757DF8EDB6EFAA758AB187EA50F1
6D630C178E30C117FE012FE83AD8537BE6BC436B2558272E2F0BF27D29972CC64D6
8AE61B3F9E03CB30954C361E333552DAB7A2EA76BE8BA7C032C98773179653F4ED2
36BE677027B7AA8A013CB6E1049597393955C86EB6678523C9CE9E7EE0995BA3A26
0B
32D8BD35CEEDD2E2ED57CB056C3FAA33E8408D10A4E846704FA9A7C94A09AED71
83DA507CA7BC51BD8B4A5244DF82A8C0C914CFC5B8F7D6CB8FAD49B56FED80ABBB9
42C23CAA4C7026CE36B32049BC2F690CB43CCB36319DBAF686B53651747BF12A835
080F1FDB1BD035D30216BFDAAF8F2994D592A45AAB8F96474412944D663FBEF2872
2ECA63EE79B0E1BF854AAECBD97D9BD80EC47AF60575B78FB0FE3ED0FC3BA0D2D00
130D2872EDBFDB4D13B8CB6E9AD2FB7F5B665D656C42FC4FAC505795566192B894E
790CC882C29D86BE54FA60F25DCA6D501E1DC4AFA9BDD6A73DBB0F556A14F2243CB
8EEA8BE8AD800F155DB0D07151369E07D6234498A8169
49B06FA8E4B17CD287F1A2
82D24D6BA6DF538D15B2D6539369CED03B706C726A329AD5F1473D5A7E67944A75F
7AE5CF0E68D2CFE4A807E8A99BD20D61BC27C5190A77069507D1978EEB239FBA4E4
798B30409DCF77708B8110E614CB5CEB4ED0FD829B1C5B6DA9D2F2894ABA571CDF7
78B36F398929CAB0774D00BE28B64507AEFD20D1B5471E6C211C7D99515FA9A2FD5
0210420AB2C1829AECCBE59B41BB4FD6B5E2C5787F17500971038A7EF37D2D80BF7
116095C8667DF7ED08606410554E8780334F8A560CD7194F584EE527333D62DCD66
AFF919E9DF6303F73D958DDEEA334E00B289E53B9B7DBE78798002CE5A97BDCC8C6
80C0254AEAC678631B87C
3173372E17E3FBE9F5B6CB0BC37FFC77360D6AA4240926
E1AA3153E4B51F0FD53F5E60F044A8FA16AE04B2292D424268A3BB48BDD71C62A16
CF428F0F97607983F78CCED15117A56EE56B2FCBAA531607A419889240C9A0CBA7C
470FD446F230837B8D9E4990D1ABFD85C0558043A29BAD480ECEF8A634521D0C9AD
0DAE814406EA8755FB2460E57183E0A307A2CF98899C01C5BC20E14D748010F9598
289C6FCCFC77E3F8428DD1A57DE5B9C8A9963C96F3BA7FC754181C61436BC82B0F4
CE50E380AB081F3DD926B56EFA7593390F53092B26E91FC477C72C0D25A574F175E
6FEA4B050BDB17500A8BE70D0638482F3322B5F538C2FB4CB2F78933D035AA38
6DF
7C4E0AF907147B5C118F3B36C7604EA14CD1C35604FED6EC22E0B4B7242935EC719
2C6E66017E6C29B86B55AC088779078D7999FFBE1BFC65E1C0D706142279E3E3068
6B6885A2927E64070E3C1D73CCAC29A69EFA88B954772769219F27E08FFB12AC936
135A4BB05241619DF2E931751CBA5C7E3B85F913CA69AB37AB7EB449BAD4F0D8F35
7A96F228AF6566AEE9171EA578A84D5BE09237AFB4655F7920C2446A07AA72F4421
64C796D3B901E2F700DB679311F956375ABBE37AB38E0F110FA38546B32A82B63CF
EBBF36B7E1F54C33D85BD402499A5EBA6F51FCD156999CFE0F18723ABD9BD964E31
952D4067614268293F9DF01093F1D4CE4FFEBAA4
240AD6B8F17E4E36049F09AFEF0
3C13B559453EF6EEED39D4B56DE64F22179194856E26FD29D1FDFC3441E25626337
95A0BC124F12500E524E51983F2EABEE535E9BE008FBA212EAB504942E64DD819A3
A6FB65C4E3294F664AC9ECA55BB166D67D4353760F31F7B3CB27C5A642731710EC9
C4F7D4664E7319E5DDFC656E312E1FB40BB5F5BB43D93178EAEEF743A24A2A7922B
8B53006ECE40D957EF2C76D13A6C7294E0AB8CB1EEC3AEE3FE935D224528F46CD15
2926ABC9F0AFA70F6253F315EA302EB27FCF7E387AD41A3517127A342356684EA32
39626EDA1A7015F29420CAB60B279A9806A3D7AC4099ACA442D0F39ABE71B9F705F
98348CD7E61893BF
60AC6CBA6BB56DC621D23D651556B58102EE52B942A7B881329
4698068D6DF12C331D266ED5741FC24E25E53B69048F405865A29DD22A1329CA616
B9EB195439A99BB0B833AB7B21E833B2262BB79077042812CC02D31628F9F4DC5E5
384C468FB6AEC3A1323179E0C01740737A9AADF0A80196E7F887F45A554FB090C4E
737C3D2CE691BE636E78F38C7107EC5311056CDB2D69671FE21857F4993A02546EA
B948B1416BFD8B6DD3917BBAEE5DB9784A8FAE862D1CA044607E182869BDBAC5FF4
DC9B7F903C5065E6185FF60D7869519071B9AB8975C8724A7BC4B97C763EE764E1D
1F4EF568E89044119A9684F99417C57CD5AC274BE0951926094E16329D7
691F2729
72B720F9F15B77E51085D30E422DE770B39FD46C999222D337B54DC9201CE2A09E8
3046866F3F61989363B22769C62D9ED016A3D5869F459932A3428F2CD9A949BB40D
8FF9205E3460E051811786439CFDA2867D8DC76030DB625D8773342A0F9367E14AF
FCFC466748289202663B70B473F635DBD89964F2DE95CA0F48BF5E13369D7B440C8
C2430757DF8EDB6EFAA758AB187EA50F16D630C178E30C117FE012FE83AD8537BE6
BC436B2558272E2F0BF27D29972CC64D68AE61B3F9E03CB30954C361E333552DAB7
A2EA76BE8BA7C032C98773179653F4ED236BE677027B7AA8A013CB6E10495973939
55C86EB6678523C9CE9E7EE0995BA3A260B


Toda esta parrafada para encriptar el texto que he puesto....vaya tela!, esto es indescifrable!. Donde radica el problema?, en que solo entrego el texto cifrado y la clave pública d. Luego si quisiera desencriptar todo este texto, necesitaria obtener la clave privada y calcular p y q para otra vez volver a pasar el algoritmo y desencriptar el texto.

Existen cifradores y decifradores online, como el de la página de Justin Wong-Chung : http://www.gax.nl/wiskundePO/#
O por ejemplo el que tienen mis amigos de Yahira
http://www.yashira.org/index.php?mode=RSA
Creado por Roger Morrison de la universidad de Oregon.

Bien, ahora ya sabeis como funciona un poco el algoritmo, y las cosas que se pueden hacer con el, ya que és muy potente, muy seguro y podemos encontrar muchos algoritmos de implementación del mismo por la web. El de mi aplicación lo saque de una web de codificación en Java, y solo tuve que modificarlo un poco para poder crear claves aleatórias. Solo hay que tener en cuenta como trabaja la libreria de Java para los enteros grandes:

import java.math.BigInteger;

Y como podemos realizar cálculos mediante esta libreria. También he encontrado librerias que funcionan en Delphi, pero su implementación no me acaba de gustar ya que la libreria no está muy bien buscada y genera algún Access Violation de vez en cuando. Con la de Java no he tenido nunca ningún problema.

  • Factorización Elíptica:
Como os he comentado antes, ¿¿ qué problema tenemos con los números grandes???, pues que no los podemos factorizar. La factorización de un número consiste en obtener los dividores de ese número, por ejemplo si quisieramos obtener la composición de 10810800 seria:
2 x 2 x 2 x 2 x 3 x 3 x 3 x 5 x 5 x 7 x 11 x 13

Cuando los números son muy grandes no se conoce ningún algoritmo que resuelva eficientemente este problema; un reciente intento de factorizar un número de 200 dígitos (RSA-200) tardó 18 meses y consumió más de medio siglo de tiempo de cálculo. Su supuesta dificultad es el núcleo de ciertos algoritmos criptográficos, como el RSA. Muchas áreas de las matemáticas y de las ciencias de la computación, como la teoría algebraica de números, las curvas elípticas o la computación cuántica, están relacionadas con este problema.

Aquí entra Hendrik Lenstra que es el que descubre la factorización eliptica con curvas también llamado Elliptic Curve Method (ECM). No voy a entrar en detalle con este tema, ya que seria bastante aburrido empezar con la notación matemática, y que seguro podemos encontrar mucha información por la red. Aquí os dejo un par de enlaces para los que queras profundizar el tema:

http://h4ck1t.blogspot.com/2008/01/factorizacin-iv-el-mtodo-de-curva.html
http://es.wikipedia.org/wiki/Factorizaci%C3%B3n_de_enteros

En la página de Dario Alpern, podemos encontrar un pequeño applet que calcula la factorización de un número mediante el método del ECM, donde podemos encontrar el código fuente del applet y en esta página, podemos encontrar la implementació libre más rápida del ECM llamada GMP-ECM.

Por ejemplo en la siguiente imagen podemos ver un ejemplo con un número bastante grande, con el que no podriamos tratarlo mediante un algoritmo simple:


Podemos ver que el tiempo que ha tardado en tratarlo ha sido mínimo, tan solo 1 segundo!.

Otro ejemplo utilizando utilizando el cifrado RSA online de Yashira:



Si tengo tiempo y puedo, subiré mi aplicación para que la podais probar (igual que todas las otras), y podais utilizar el algoritmo RSA.

espero que os haya sido de utilidad, nos vemos!.

  • fuentes:
http://es.wikipedia.org/wiki/Factorizaci%C3%B3n_de_enteros
http://es.wikipedia.org/wiki/Claves_RSA
http://www.yashira.org/index.php?mode=RSA
http://www.alpertron.com.ar/ECMC.HTM

0 comments:

Post a Comment