marcos@caus-dp.UUCP (Marcos R. Della) (11/23/87)
+------------ | In article <283@caus-dp.UUCP> you ask... | | The basic theory they use is to convert your code to integer values | below some value K where K is the product of two large primes (call them | P and Q) There is one caveat on P and Q, neither (P - 1) or (Q - 1) can | be divisible by three or the system will not work. | | Now to encrypt, simply cube the cleartext message mod K, where K is | regarded as the public encryption key. | | To decrypt, evaluate the decryption key D such that | | D = (2 * (P - 1) * (Q - 1) + 1] / 3 | | and decryption of a block B is simply (B ^ D) MOD K | | i.e. | | T: plaintext, C: ciphertext | | C = (T ^ 3) MOD K | T = (C ^ D) MOD K | | where K = P * Q (P and Q both primes w/ other caveats & restrictions) | K is public key. | and D = (2 * (P - 1) * (Q - 1) + 1] / 3 | D is private decryption key. | | A couple of limitations on P and Q will make factorisation of K more | difficult: | | arrange P and Q so that both (P - 1) and (Q - 1) contain at least | one large prime factor | the ratio P / Q should not approximate a simple fraction (i.e. | 1/2, 2/3, 3/4, etc. etc. etc.) | | dg@wrs.UUCP - David Goodenough +---------- I have spent some time pouring through this description and have not yet been able to produce anything that will work with it. My problem lies in the section that says T = (C ^ D) MOD K. The problem I face is that D is a large number and anything taken to a large number is rediculous in size. Does someone have a fix that will make this a better system or maybe another method that might not be as secure, but will still work on the same principle of the encrypt and decrypt keys? Any help would be appreciated... Marcos R. Della -- ...!lll-crg -> !csustan -\ | Whatever I said doesn't ...!sdsu ----->->!polyslo!caus-dp!marcos | mean diddly as I forgot ...!ihnp4 -> !csun ----/ | it even before finishing ...!dmsd ---/ | typing it all out!!!
srt@duke.cs.duke.edu (Stephen R. Tate) (11/24/87)
In article <291@caus-dp.UUCP> marcos@caus-dp.UUCP (Marcos R. Della) writes: > >I have spent some time pouring through this description and have not yet >been able to produce anything that will work with it. My problem lies in >the section that says T = (C ^ D) MOD K. The problem I face is that D is >a large number and anything taken to a large number is rediculous in size. > But you are taking C^D MOD K. Therefore the number will be no larger than K. If you are worried about size at intermediate calculations, how were you planning on doing the powering? You should do it by repeated squaring, and at each step do the reduction modulo K. That way all intermediate calculations will be less than twice the number of bits in K. (This is not very unreasonable.....) Does this clear things up? -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt@cs.duke.edu "There ain't nothin' in the world that a T-Bone Shuffle won't cure."
kwalker@arizona.edu (Kenneth Walker) (11/24/87)
In article <291@caus-dp.UUCP>, marcos@caus-dp.UUCP (Marcos R. Della) writes: > My problem lies in > the section that says T = (C ^ D) MOD K. The problem I face is that D is > a large number and anything taken to a large number is rediculous in size. > Just as multiplication can be implemented by shifting and adding, exponentiation can be implemented by squaring and multiplying (see Knuth, "The Art of Computer Programing" vol 2). The fact that (a * b) mod K = ((a mod K) * (b mod K)) mod K lets you reduce your result modulo K after every squaring and every multiplication without affecting the end result. If you do this, the intermediate results will always be less than K ^ 2.
wmcb@ecsvax.UUCP (William C. Bauldry) (12/09/87)
In article <291@caus-dp.UUCP> marcos@caus-dp.UUCP (Marcos R. Della) writes: >the section that says T = (C ^ D) MOD K. The problem I face is that D is >a large number and anything taken to a large number is rediculous in size. > >Does someone have a fix that will make this a better system or maybe >another method that might not be as secure, but will still work on the >same principle of the encrypt and decrypt keys? > >Any help would be appreciated... > >Marcos R. Della Aside from the usual pointers to represent the power in terms of squares and take mod k at each opportunity in intermediate calculations, the main thought to keep in mind is the security of Public Key systems is based on the *difficulty* of arithmetic (in particular factoring large numbers) that comes up in en/de-crypting. i.e. it can't be too easy or it's not secure. If your not really worried about security, then instead of the system above (based on the RSA scheme) you could switch to a Trapdoor type of coding where the arithmetic is much simpler - back in 1976/7 Scientific American had a very good article on both these systems. Best of luck. Bill Bauldry Dept of Math Sci Appalachian State U Boone, NC