From: tad.bochan@... Date: 2004-08-30T19:27:09+09:00 Subject: Réf. : ASCII, RSA AND BIGNUM --0__=4EBBE593DFA10B4C8f9e8a93df938690918c4EBBE593DFA10B4C Content-type: text/plain; charset=iso-8859-1 Content-transfer-encoding: quoted-printable Hi Barry, I'm a total ruby-nuby, so ther's not much ruby content here. In the RSA algorithm, you need to be able to evaluate a**b mod n using integer arithmetic only. (Note : "mod n" means "remainder after division by n". ) The easiest way to describe the standard method is by a somewhat contrived example. Let's say you want to calculate A=3D(25800**100 mod 257) First, note that 100 base 10 =3D 1100100 base 2, so that 100**100 =3D (100**64) * (100**32) * (100**4) Now calculate, 25800**1 mod 257 =3D 100 100**2 mod 257 =3D 100*100 mod 257 =3D 235 100**4 mod 257 =3D 235*235 mod 257 =3D 15 100**8 mod 257 =3D 15*15 mod 257 =3D 225 100**16 mod 257 =3D 225*225 mod 257 =3D 253 100**32 mod 257 =3D 253*253 mod 257 =3D 16 100**64 mod 257 =3D 16 * 16 mod 257 =3D 256 Then, A =3D ((256 * 16) mod 257) * (15 mod 257) A=3D ( 241 * 15) mod 257 So, the answer is A=3D17 You can see that that no calculation above requires more than 5 digits (257**2 =3D 66049) Specialized languages like Wolfram's Mathematica handle this sort of calculation very efficiently for large values of a,b and n. I hope this is useful to you. Regards, Tad (Embedded image moved to file: pic29358.pcx) Internet barry@angleinc.com - 27/08/2004 23:07 Veuillez r=E9pondre =E0 ruby-talk@ruby-lang.org Pour : ruby-talk cc : Objet : ASCII, RSA AND BIGNUM Continuing on the track of the previous question about ASCII, I'm using each_byte to change a string to ASCII for the purpose of encrypting it, using the theory of the RSA algorithm ( to see if I can! ). Part of this algorithm requires getting a power ( a**b ) in which the "a" is the ASCII value of the string and the "b" is some large number that is dictated by the RSA algorithm ( about 25,000,000,000,000 for my test string ). However, when I do this I get the error NaN test_ascii.rbw:20: warning: in a**b, b may be too big While I could simulate a power with a loop, doing this 25 trillion times might take a little while. I could also simulate the power with logs, but I'm sure that this would add inaccuracies and the integral number has to be exact. Is there a way out or is this just a fundamental limitation of Bignums in Ruby? Barry This message and any attachments (the "message") is intended solely for the addressees and is confidential.=20 If you receive this message in error, please delete it and=20 immediately notify the sender. Any use not in accord with=20 its purpose, any dissemination or disclosure, either whole=20 or partial, is prohibited except formal approval. The internet can not guarantee the integrity of this message.=20 BNP PARIBAS (and its subsidiaries) shall (will) not=20 therefore be liable for the message if modified.=20 --------------------------------------------- Ce message et toutes les pieces jointes (ci-apres le=20 "message") sont etablis a l'intention exclusive de ses=20 destinataires et sont confidentiels. Si vous recevez ce=20 message par erreur, merci de le detruire et d'en avertir=20 immediatement l'expediteur. Toute utilisation de ce=20 message non conforme a sa destination, toute diffusion=20 ou toute publication, totale ou partielle, est interdite, sauf=20 autorisation expresse. L'internet ne permettant pas=20 d'assurer l'integrite de ce message, BNP PARIBAS (et ses filiales) decline(nt) toute responsabilite au titre de ce=20 message, dans l'hypothese ou il aurait ete modifie. --0__=4EBBE593DFA10B4C8f9e8a93df938690918c4EBBE593DFA10B4C Content-type: application/octet-stream; name="pic29358.pcx" Content-Disposition: attachment; filename="pic29358.pcx" Content-transfer-encoding: base64 CgUBCAAAAAAGARMAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAABBwEBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAD////////m/9P/yf/F/8L/wf/////////m/9P/yf/F/8L/wf/////////m /9P/yf/F/8L/wf/////////m/9P/yf/F/8L/wf/////////m/9P/yf/F/8L/wf/G/8IA1P/CAMX/ xADE/8QA0P/FAMX/xADH/wDS/8IAxP/FANH/xQDD/8UAw//FAND/xQDE/8UAxP/EANP/wgDH/8QA z//FAMP/xQDG/8QAwv/B/8T/wgDB/wDS/8IAwf8AxP8AxP8Awv8AxP8Azv8Axf8Awv/CAMT/AMX/ wgDQ/8IAwf8AxP8A1P8Axf8Awf8Axf8Awv8A0/8Axf8Aw/8Axv/CAMT/AND/wgDB/wDG/wDS/wDF /wDC/wDJ/wDE/8L/wf/H/wDV/wDE/wDE/wDC/wDE/wDO/wDF/wDI/wDE/wDB/wDT/wDE/wDU/wDF /wDB/wDF/wDC/wDT/wDF/wDD/wDM/wDT/wDF/wDT/wDF/wDC/wDI/wDF/8L/wf/H/wDV/wDE/wDE /wDC/wDE/wDU/wDI/wDD/wDC/wDT/wDE/wDa/wDH/wDC/wDZ/wDD/wDM/wDT/wDE/wDY/8L/AML/ AMf/AMX/w//B/8f/ANX/AMT/AMT/AML/AMT/ANP/AMb/wwDE/wDC/wDT/wDE/8UA1f8Ax/8Aw//F ANT/AMT/xQDF/8MA1P8AxP8Awf/EANT/AMP/xQDD/wDB/8QAw//B/8f/ANX/AMT/AMT/AML/AMT/ ANH/wgDJ/wDD/wDD/wDT/wDJ/wDS/8IAxv/CAMn/ANH/wgDK/wDG/wDU/wDE/8IAxP8A0f/CAMn/ AML/wgDE/wDC/8H/x/8A1f8AxP8AxP8Awv8AxP8A0P8AzP8Awv/GANL/AMn/ANH/AMf/AMv/AND/ AMz/AMf/ANP/AMT/AMX/AND/AMv/AML/AMX/AML/wf/H/wDG/8IAzf8AxP8AxP8Awv8AxP8Aw//C AMr/AM3/AMb/AMT/wgDN/wDJ/wDE/8IAyv8Ax/8AzP8Aw//CAMr/AM3/AMf/AMP/wgDO/wDE/wDF /wDD/8IAyv8AzP8Awv8Axf8Awv/B/8f/AMb/AM7/AMT/AMT/AML/AMT/AMP/AMr/AMX/AML/AMX/ AMb/AMT/AM7/AMP/AMX/AMT/AMr/AMX/AMH/AMX/AMH/AMX/AMP/AMr/AMX/AML/AMX/AMH/AMX/ AMP/AM//AMT/AMX/AMP/AMr/AMX/AMH/AMX/AML/AMX/AML/wf/E/8cAwv/CAMv/xwDC/8QAxP/E AMP/wgDK/8cAw//FAMX/xADC/8IAy//HAMH/xQDE/8IAyv/HAMH/xwDC/8UAw//CAMr/xwDD/8UA w//FAMP/wgDM/8cAwv/FAMP/wgDK/8cAwv/FAMT/xQDD/8H/zf8A5P8A5f8A3f8A5P8A5f8A3v8A 1P/K/8X/wv/B/83/AOT/AOX/AN3/AOT/AOX/AN7/ANT/yv/F/8L/wf/////////m/9P/yf/F/8L/ wf/////////m/9P/yf/F/8L/wf/////////m/9P/yf/F/8L/wf8MAAAAgAAAAIAAgIAAAACAgACA AICAwMDAwNzApsrwQCAAYCAAgCAAoCAAwCAA4CAAAEAAIEAAQEAAYEAAgEAAoEAAwEAA4EAAAGAA IGAAQGAAYGAAgGAAoGAAwGAA4GAAAIAAIIAAQIAAYIAAgIAAoIAAwIAA4IAAAKAAIKAAQKAAYKAA gKAAoKAAwKAA4KAAAMAAIMAAQMAAYMAAgMAAoMAAwMAA4MAAAOAAIOAAQOAAYOAAgOAAoOAAwOAA 4OAAAABAIABAQABAYABAgABAoABAwABA4ABAACBAICBAQCBAYCBAgCBAoCBAwCBA4CBAAEBAIEBA QEBAYEBAgEBAoEBAwEBA4EBAAGBAIGBAQGBAYGBAgGBAoGBAwGBA4GBAAIBAIIBAQIBAYIBAgIBA oIBAwIBA4IBAAKBAIKBAQKBAYKBAgKBAoKBAwKBA4KBAAMBAIMBAQMBAYMBAgMBAoMBAwMBA4MBA AOBAIOBAQOBAYOBAgOBAoOBAwOBA4OBAAACAIACAQACAYACAgACAoACAwACA4ACAACCAICCAQCCA YCCAgCCAoCCAwCCA4CCAAECAIECAQECAYECAgECAoECAwECA4ECAAGCAIGCAQGCAYGCAgGCAoGCA wGCA4GCAAICAIICAQICAYICAgICAoICAwICA4ICAAKCAIKCAQKCAYKCAgKCAoKCAwKCA4KCAAMCA IMCAQMCAYMCAgMCAoMCAwMCA4MCAAOCAIOCAQOCAYOCAgOCAoOCAwOCA4OCAAADAIADAQADAYADA gADAoADAwADA4ADAACDAICDAQCDAYCDAgCDAoCDAwCDA4CDAAEDAIEDAQEDAYEDAgEDAoEDAwEDA 4EDAAGDAIGDAQGDAYGDAgGDAoGDAwGDA4GDAAIDAIIDAQIDAYIDAgIDAoIDAwIDA4IDAAKDAIKDA QKDAYKDAgKDAoKDAwKDA4KDAAMDAIMDAQMDAYMDAgMDAoMDA//vwoKCkgICA/wAAAP8A//8AAAD/ /wD/AP////// --0__=4EBBE593DFA10B4C8f9e8a93df938690918c4EBBE593DFA10B4C--