Method and apparatus for memory efficient variants of public key encryption and identification schemes for smart card applications

摘要

Memory efficient variants of public key encryption and identification schemes for smart card applications with severely limited RAM without using dedicated coprocessors. The variants replace the memory-intensive modular multiplication operation z=x*y (mod n) by a new randomized multiplication operation z'=x*y+r*n, where r is a randomly chosen integer in a suitable range [0,b], and a double convolution process to compute z' is used. Method and apparatus are described.