Searching \ for '[PIC]: RSA encryption' in subject line. ()
Help us get a faster server
FAQ page: www.piclist.com/techref/microchip/devices.htm?key=pic
Search entire site for: 'RSA encryption'.

Exact match. Not showing close matches.
'[PIC]: RSA encryption'
2000\08\05@191604 by

I've been asked if RSA encryption is feasible on a PIC. As it was
explained to me, the calculation required is

M = ( E^ (P * Q) ) mod B

where M, E and B are 1024-bit strings, P and Q are 512-bit prime
numbers, (not necessary for PIC to generate these private keys)

I gave a very hesistant "maybe", mainly because of the scale and
processing time, not the maths itself. Has anyone any experience
with such a large calculation ?

TIA

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestmitvma.mit.edu>
>I've been asked if RSA encryption is feasible on a PIC. As it was
>explained to me, the calculation required is
>
>M = ( E^ (P * Q) ) mod B
>
>where M, E and B are 1024-bit strings, P and Q are 512-bit prime
>numbers, (not necessary for PIC to generate these private keys)
>

My 1st thought would be that the calculation would be possible but that the
storage needed for an in place calculation exceeds typical PIC internal RAM
capacity.
A 1024 bit number takes 128 Bytes so total for 2 x 1024 & 2 x 512 = 384
bytes of RAM (assumes product appear in another register) plus some other gp
support RAM.

Could do with external serial RAM or port addressed RAM but way slow or pin
and hardware intensive or unwieldy.

My 1st question would be "why a PIC" surely there are other devices much
better architecturally suited to this.

Russell McMahon
_____________________________

What can one man* do?   Help the hungry at no cost to yourself!
at  http://www.thehungersite.com/
(* - or woman, child or internet enabled intelligent entity :-))
From other worlds:
http://www.changingourworld.com    http://www.easttimor.com   http://www.sudan.com

--

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]: PIC only [EE]: engineering [OT]: off topic [AD]: advertisements
> >M = ( E^ (P * Q) ) mod B
> >
> >where M, E and B are 1024-bit strings, P and Q are 512-bit prime
> >numbers, (not necessary for PIC to generate these private keys)
>
> My 1st thought would be that the calculation would be possible but that
the
> storage needed for an in place calculation exceeds typical PIC internal
RAM
> capacity.
> A 1024 bit number takes 128 Bytes so total for 2 x 1024 & 2 x 512 = 384
> bytes of RAM (assumes product appear in another register) plus some other
> gp support RAM.
>
> Could do with external serial RAM or port addressed RAM but way slow or
pin
> and hardware intensive or unwieldy.
>
> My 1st question would be "why a PIC" surely there are other devices much
> better architecturally suited to this.

>       Russell McMahon

I could have asked about Mot or AVR, but as this is the Piclist......;-)

My feeling was that internally the PIC may be deficient in RAM. The maths
haven't been done to approximate how much working room is needed. If
an AVR with some external memory will do the job, then that's what we'd
try.

The other question is speed.  The person who asked is a programmer
for a local ISP and knows how long ID takes on a secure web site (pretty
quick, in human terms, eg for a credit card authentication), but he has no
working knowledge of micros. His thought was to use an 'x86 chip, but I've
suggested to him that would probably be impractical for the application he
has in mind, so therefore micros are being looked at. I'd really like some
ball-park idea of how long it would take to do this calculation. If it's
going
to take 20-30 seconds on even the fastest micro, the idea can't go ahead
in its proposed form. It has to be reasonably comparable in time to an
on-line verification

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]: PIC only [EE]: engineering [OT]: off topic [AD]: advertisements
G'Day,

I had to do this a few years ago ang found that the simplest solution was a
cylink (from memory) part that did the multiplication / division for you.
From memory you just clocked in the values you wanted worked on and it did
the hard work for you (real fast too).

Of the top of my head I can't remember the part number (but I could look it
up if your interested).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mike Cornelius                  Internet: mikebytethis.com.au
Byte This Interactive           Phone:    +61 2 9310-2157
PO Box 1342 Strawberry Hills    FAX:      +61 2 9319-3948
NSW 2012 Australia              URL:      http://www.bytethis.com.au
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

{Original Message removed}
> followed by the modulo operation can be simplified. BTW, Eric Smith has
> implemented the DES algorithm in a PIC.

Sorry, I asked about Eric Williams in last post, thinking of somebody else,
should have asked how to get in touch with Eric Smith and whether it was
DES or 3DES he'd implemented

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
The RSA algorithm is not well suited to an 8-bit processor without hardware
multiplication, but there are several other very good algorithms that were
designed with "smart card" implementations in mind.

NIST is conducting a process to replace DES as the standard, and has a list
of 5 finalists posted at the following website:
http://csrc.nist.gov/encryption/aes/
Smartcard implementation is one of the considerations for these algorithms,
so there are reference smartcard implementations posted for several of them,
usually 68HC11, but if it can be done on a 68HC11, it can probably be done
on a PIC.

I've coded Rijndael for a PIC16C63, and it's not too shabby.  It needs about
50 bytes of RAM, a few hundred words of code, and encrypts or decrypts a
16-byte block in a few thousand cycles.  Unfortunately I'm not free to post
the code, but it wasn't extremely difficult to translate it from the 68HC11
code posted on the web (the worst part is that the 68HC11 programmer was in
love with macros, which makes the code an extremely hard puzzle to crack).

Rijndael has been released to the public domain so you can use it freely,
though a crack has been found for a reduced version of the algorithm, so it
may not be the strongest one in existence.

The TwoFish algorithm is also reputed to be readily implemented on small
processors, but I haven't had spare time to try tackling it, so I can't say
whether it is doable on a PIC.

Another compact algorithm that is especially easy to implement is the
now-declassified Skipjack that the feds were once trying to force down
everyone's throat along with key escrow:
csrc.nist.gov/encryption/skipjack-kea.htm
The spec is an easy-to-follow recipe for writing the code for the algorithm.
The federal government owns a patent on it, and there has been no public
announcement that I have been able to find to indicate that it has been
released.

> {Original Message removed}
Jinx wrote:
<snip>
> My feeling was that internally the PIC may be deficient in RAM. The maths
> haven't been done to approximate how much working room is needed. If
> an AVR with some external memory will do the job, then that's what we'd
> try.
>
> The other question is speed.  The person who asked is a programmer
> for a local ISP and knows how long ID takes on a secure web site (pretty
> quick, in human terms, eg for a credit card authentication), but he has no
> working knowledge of micros. His thought was to use an 'x86 chip, but I've
> suggested to him that would probably be impractical for the application he
> has in mind, so therefore micros are being looked at. I'd really like some
> ball-park idea of how long it would take to do this calculation. If it's
> going
> to take 20-30 seconds on even the fastest micro, the idea can't go ahead
> in its proposed form. It has to be reasonably comparable in time to an
> on-line verification

Could you do this on a PC-104 (or \$\$ Tiqit) or other small 80x86 SBC,
perhaps?  Not as cheap as a PIC, but (for some SBC's) quite cheap (For
example in 1000's the http://www.star.net/people/~mvs/ 3"x4" Mini PC is
\$27, \$95 for an Eval kit.)  I, too, wish the PICs had about 16k of RAM
<G>  (AT90S8515's do interface to SRAM reasonably easily.)

Mark

--
Detest spam?  Take the Boulder Pledge, boycott SPAMmers.
http://www.zdnet.com/yil/content/mag/9612/ebert9612.html

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
On Mon, Aug 07, 2000 at 04:25:05PM -0700, Mark Willis wrote:
> Jinx wrote:
> <snip>
>
> Could you do this on a PC-104 (or \$\$ Tiqit) or other small 80x86 SBC,
> perhaps?  Not as cheap as a PIC, but (for some SBC's) quite cheap (For
> example in 1000's the http://www.star.net/people/~mvs/ 3"x4" Mini PC is
> \$27, \$95 for an Eval kit.)  I, too, wish the PICs had about 16k of RAM
> <G>  (AT90S8515's do interface to SRAM reasonably easily.)
>

Just one (but important) point. When implementing RSA (or other public key
algorithm) in non-single-IC environment you must be aware of security
issues. If your device is to be used as an "electronic key" and the protocol
is based on challenge-response method, then it can be implemented
in that way, that obtaining the private key (and making a copy of the key)
is impossible, even if someone has full access for your device.
It is much more difficult to do it that way, when you use the external RAM.
Analysis of transfers between uC and RAM may result in private key
compromise :-(.
--
Wojciech M. Zabolotny
http://www.ise.pw.edu.pl/~wzab  <--> wzabise.pw.edu.pl

Before buying any hardware ask the dealer if it is Open Source friendly!!!
hhtp://http://www.openhardware.org

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.
> It is much more difficult to do it that way, when you use the external
RAM.
> Analysis of transfers between uC and RAM may result in private key
> compromise :-(

The plan was to encapsulate any devices so that an attempt to find
any worthwhile measuring spot in the circuit would kill it :-)

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.
> has in mind, so therefore micros are being looked at. I'd really like some
> ball-park idea of how long it would take to do this calculation. If it's
> going
> to take 20-30 seconds on even the fastest micro, the idea can't go ahead
> in its proposed form. It has to be reasonably comparable in time to an
> on-line verification

I vaguely recall that opening a 1024bit PGP email on my old 68030-25MHz based
computer was pausing it for 1-2 seconds.

So I wouldn't try RSA on PIC nor AVR. That is something for specialized chips
or modern 32+ bit CPUs.  Not necessarily x86, can also be ARM or 68xxx or ...
There exist RSA co-processors by the way, but I can't name any.

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

> The plan was to encapsulate any devices so that an attempt to find
> any worthwhile measuring spot in the circuit would kill it :-)

Remember that when you deliver more than 1 device, the attacker can
practice on the 1st, and carry out the attack on the 2nd.

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

> There exist RSA co-processors by the way, but I can't name any.

Knowing they exist is a plus

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

> > The plan was to encapsulate any devices so that an attempt to find
> > any worthwhile measuring spot in the circuit would kill it :-)
>
> Remember that when you deliver more than 1 device, the attacker can
> practice on the 1st, and carry out the attack on the 2nd.

Yes, that's a good point. But if there's a 1024-bit key involved, and s/w
is tied up in an unreadable micro, the effort required to get a micro out
of a block of epoxy, then try to get the s/w out, then break the key should
be a pretty big deterrent. I hope. I've tried myself to get chips out of
epoxy, not easy, even with a normal circuit. A flimsy one, say with fine
wires and SMT components, would be pretty tricky to get out in one piece

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

----- Original Message -----
From: "Jinx" <joecolquittCLEAR.NET.NZ>
To: <PICLISTMITVMA.MIT.EDU>
Sent: Wednesday, August 23, 2000 11:28 PM
Subject: Re: [PIC]: RSA encryption

> > > The plan was to encapsulate any devices so that an attempt to find
> > > any worthwhile measuring spot in the circuit would kill it :-)
> >
> > Remember that when you deliver more than 1 device, the attacker can
> > practice on the 1st, and carry out the attack on the 2nd.
>
> Yes, that's a good point. But if there's a 1024-bit key involved, and s/w
> is tied up in an unreadable micro, the effort required to get a micro out
> of a block of epoxy, then try to get the s/w out, then break the key
should
> be a pretty big deterrent. I hope. I've tried myself to get chips out of
> epoxy, not easy, even with a normal circuit. A flimsy one, say with fine
> wires and SMT components, would be pretty tricky to get out in one piece

Someone earlier posted the link to a fascinating paper at
http://www.cl.cam.ac.uk/users/rja14/tamper.html on breaking secure chips
which included inter alia a very simple looking method of etching away epoxy
coatings.

.

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

On Thu, 24 Aug 2000, Jinx wrote:

> Yes, that's a good point. But if there's a 1024-bit key involved, and s/w
> is tied up in an unreadable micro, the effort required to get a micro out
> of a block of epoxy, then try to get the s/w out, then break the key should
> be a pretty big deterrent. I hope. I've tried myself to get chips out of
> epoxy, not easy, even with a normal circuit. A flimsy one, say with fine
> wires and SMT components, would be pretty tricky to get out in one piece

Three words...  one solution:

Methyl ethyl ketone.

Dale
---
The most exciting phrase to hear in science, the one that heralds new
discoveries, is not "Eureka!" (I found it!) but "That's funny ..."
-- Isaac Asimov

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

> From: Andy Howard

> Someone earlier posted the link to a fascinating paper at
> http://www.cl.cam.ac.uk/users/rja14/tamper.html on breaking secure chips
> which included inter alia a very simple looking method of etching away
epoxy
> coatings.

Nice one - food for thought

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

----- Original Message -----
From: Dale Botkin <daleBOTKIN.ORG>
To: <PICLISTMITVMA.MIT.EDU>
Sent: Thursday, August 24, 2000 12:02 AM
Subject: Re: [PIC]: RSA encryption

> On Thu, 24 Aug 2000, Jinx wrote:
>
> > Yes, that's a good point. But if there's a 1024-bit key involved, and
s/w
> > is tied up in an unreadable micro, the effort required to get a micro
out
> > of a block of epoxy, then try to get the s/w out, then break the key
should
> > be a pretty big deterrent. I hope. I've tried myself to get chips out of
> > epoxy, not easy, even with a normal circuit. A flimsy one, say with fine
> > wires and SMT components, would be pretty tricky to get out in one piece
>
> Three words...  one solution:
>
> Methyl ethyl ketone.

A pun?

{Quote hidden}

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

> > Dale
> >
> > Three words...  one solution:
> >
> > Methyl ethyl ketone.
>
> Bob
>
> A pun?

I'll be a rotter back ;-)   MEK isn't a solution

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

> Three words...  one solution:
>
> Methyl ethyl ketone.
>
> Dale

OK, how's this. I started my working life as a tech in a resin lab. The
one thing we hated was polyester resin (eg fibreglass resin or
encapsulating resin) that had gelled and set in something it wasn't
supposed to. Like an expensive glass reaction pot. We never found
anything that would shift it, from organic solvents to conc hydroxides
to chromic acid, which is a very very active acid. Ask my finger. Any
comments on PE resin ? Not as convenient as epoxy, but I do have
some around from time to time, I encapsulate interesting-looking
chips and components and things into coasters

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

On Thu, 24 Aug 2000, Bob Ammerman wrote:

> > Three words...  one solution:
> >
> > Methyl ethyl ketone.
>
> A pun?

Unintentional.  Embarrassingly enough, that hadn't occurred to me until
this morning.  That'll teach me to post right before going to bed.

When I was but a wee lad (OK, maybe 16 or so) I bought some military
surplus intrusion detectors.  Each was an extremely sensitive vibration
sensor (fine spring in a little tiny can) and a VHF transmitter.  Power
was from 3 little mercury cells, and the whole thing was encapsulated in
epoxy, then rubber coated to look like a clump of dirt.  You pulled a
little pin to turn on power to the thing, then you could listen to an AM
VHF radio for clicks when something walked or drove by within a few yards.

Of course, the batteries were all stone dead, so I had to get them apart.
Dad suggested MEK.  Worked like a charm!  Rubber and epoxy gone,
components undamaged other than some plastic bits softened or dissolved.
I was impressed.  Took a couple of days, if I recall correctly.

Dale
---
The most exciting phrase to hear in science, the one that heralds new
discoveries, is not "Eureka!" (I found it!) but "That's funny ..."
-- Isaac Asimov

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.

> > > Three words...  one solution:
> > >
> > > Methyl ethyl ketone.
> >
> > A pun?
>
> Unintentional.  Embarrassingly enough, that hadn't occurred to me until
> this morning.  That'll teach me to post right before going to bed.

I've been reading the info at the link Andy Howard posted. Fuming nitric
seems to be the acid of choice for hackers wanting to get rid of epoxy.
It doesn't attack silicon or gold. Any aluminium gets an oxide coating
to protect it. I'm halfway through the 15 pages, so far it's given me plenty