Interesting concept...

A suggestion is MD5 (one way hash) instead of RSA, better suited to
microcontrollers I believe. Means the server has to walk the passcode
table, or part of the passcode is actually an ID transmitted plaintext.

More important problem: a digit is only about 3.2 bits, no one can
remember an 18 digit passcode, maybe 10 digits = 32 bits (but realisticly
more like 4 digits!). Assuming I can eavesdrop the conversation then this
is very easy to crack.

Counter-top ATM readers must have the exact same problem, how do they deal
with it? I know they have an 'encryption chip' provided by the banks but
don't know how it fits into the protocol.

> The main problem however is the choice of proper microcontroller.
> The simplest RSA implementation requires holding of "challenge" and
> result of it's exponentiantion in RAM. If "challenge" is L-bits long,
> and the RSA's N coefficient is M-bits long, than I need L-bits for
> "challenge" and L+M bits for temporary multiplication result.
> For 512-bit key (it is a minimum for practical use) the M is 1024.
> If L is 512 I need the 1536 bits = 192 bytes of RAM.
> It can't be done with 16F84 :-(. For 1024-bit key results are even worse
> and probably even the 16F87x is not sufficient.
> However maybe there is a tricky RSA implementation better suited for
> microcontroller implementation. Does anybody knows about it?