Subject:
|
Re: RCX as a PGP engine
|
Newsgroups:
|
lugnet.robotics.rcx.legos
|
Date:
|
Wed, 27 Mar 2002 06:01:16 GMT
|
Viewed:
|
1756 times
|
| |
|
|
I posted this msg. about 10 days ago but as my server was set up wrong it
didn't work. sorry for the delay.
At the time of posting this i have already seen the movie thrice so I'm
about ready.
I've recently (a month ago) created a RSA encryption/decryption program in
c++. Over thas past month i've been toying with the exact same idea that you
got, but as i had exams i couldn't get any quality work done. anyway the
theory behind RSA is pretty easy to grasp provided you give it enough
thought. It goes something like this:
R=U*V where U,V are big primes (from sensor input, whatever)
phi is Euler's totient function
phi(n) = no. of nos. from 1 to N relatively prime to N
phi(r)=(U-1)(v-1)
P*Q % phi(r) =1
Assume p to have any value then calculate q
encrypt using T^P % R = X
P and R is public key
decrypt using X^Q % R = T
Q and R is private key
The problem is in calculating X^Q%R or T^P%R. you see T to the P is a huge
number which is generally out of range of the machine. So it cant find mod R
of it.
But theres an elegant solution to this. I thought of a way to solve this
that involves fermats theorem. But calculations are too big for little old
rcx, and the solution isnt elegant (i feel).A neater method is to use
modular arithmetic and binary. Let me explain.
I found this solution to my problems while idly 'googling' one night.
say you want to find 31^29%35
26 is 2 to the 4th plus 2 to the 3rd plus 2 square
29=2^4+2^3+2^2+2^0
31^29 = 31^(2^4 + 2^3 + 2^2 + 2^0)
= 31^(2^4) * 31^(2^3) * 31^(2^2) * 31^(2^0)
= 31^(2 * 2 * 2 * 2) * 31^(2 * 2 * 2) * 31^(2 * 2) * 31
= (((31^2)^2)^2)^2 * ((31^2)^2)^2 * (31^2)^2 * 31.
This may not seem to helpful, but hang on
31^2 = 961 = 16 (mod 35).
substituting, 31^29 = (((31^2)^2)^2)^2 * ((31^2)^2)^2 * (31^2)^2 * 31 (mod
35),
gives us 31^29 = ((16^2)^2)^2 * (16^2)^2 * 16^2 * 31 (mod 35).
and calculating the square: 16^2 = 256 = 11 (mod 35),
so,
31^29 = (11^2)^2 * 11^2 * 11 * 31 (mod 35).
Now keep repeating
11^2 = 121 = 16 (mod 35)
16^2 = 256 = 11 (mod 35)
So now,
31^29 = 16^2 * 16 * 11 * 31 (mod 35)
= 11 * 16 * 11 * 31 (mod 35).
Keep using this
31^29 = 11 * 16 * 11 * 31 (mod 35)
= 11 * 16 * 341 (mod 35)
= 11 * 16 * 26 (mod 35)
= 11 * 416 (mod 35)
= 11 * 31 (mod 35)
= 341 (mod 35)
= 26 (mod 35).
And surprise surprise, the answer is 26. No crazy exponents involved.
Using this trick i think i can get my code to run in NQC. (sorry haven't
figured out legOS yet) I'll have to work out the details but the theory is
relatively sound. I think that all calculations are light enough to be
carried out by the RCX. I'll let you guys worry about random number
generation ;-). There is some sort of SetRandomSeed() command though.I've
never used it yet.
Now we can send plain text through msgs. perhaps to RCX, which encrypts and
send cypher text back through IR port.
My last exam gets over on monday and then I have to see FOTR a few times (it
just came to India and I'm a mad fan), then I'm ready to give this project
all my time.
Just for fun, heres RSA in two lines of perl!
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
thats thanks to adam back. (aba@dcs.exeter.ac.uk)
thanks for listening
aatish
aatish@mac.com
http://aatish.0catch.com Check out my site I'm working on some interesting
projects at the moment.
"David Chen" <dcchen@pacbell.net> wrote in message
news:3C77F215.759D53AA@pacbell.net...
> So I'm a bit behind on my reading list and I'm finally working through
> Steven Levy's fascinating book "Crypto" on the history and development
> of Public Key Incription and such. Great stuff.
>
> I was just thinking, would the RCX be able to implement a PGP or RSA
> type algorithm within it's tiny memory footprint given it's processing
> power?
>
> Imagine military grade encryption in a little yellow and grey Lego
> brick? I imagine a precompiled LegOS dll with the public and private
> keys built into it (Make sure you delete or eat the source code after
> compiling!!:) Then, you could squirt a plaintext message into
> the RCX via the IR tower which would then squirt out the encrypted
> message (all you'd need is a PC side program like Hyperterminal).
> Alternately, you could send it encrypted text and it would spit out
> the decrypted plaintext.
>
> Of course you would want to cover the RCX and the IR tower up with
> something like a heavy cloth or piece of clothing to keep someone from
> evesdropping?
>
> If you ever want to destroy your encoding block to keep it from falling
> into enemy hands, just pull out a couple of batteries or throw it really
> hard against a solid surface (let's hope it doesn't come to that!!) or
> hit the reset sequence and your encryption keys and engine are purged.
>
> Wow, who ever thought that the little RCX could be an export restricted
> espionage tool?
>
> I think I'll going to have a look at some of that PGP source code...:)
>
> Dave
>
> --
>
> dcchen <at> pacbell <dot> net
|
|
Message is in Reply To:
 | | RCX as a PGP engine
|
| So I'm a bit behind on my reading list and I'm finally working through Steven Levy's fascinating book "Crypto" on the history and development of Public Key Incription and such. Great stuff. I was just thinking, would the RCX be able to implement a (...) (22 years ago, 23-Feb-02, to lugnet.robotics.rcx.legos)
|
13 Messages in This Thread:
 
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
