Paper 2020/624

RSA for poor men: a cryptosystem based on probable primes to base 2 numbers

Marek Wójtowicz

Abstract

We show it is possible to build an RSA-type cryptosystem by utilizing \textit{probable primes to base 2} numbers. Our modulus $N$ is the product $n\cdot m$ of such numbers (so here both prime and some composite, e.g. Carmichael or Fermat, numbers are acceptable) instead of prime numbers. Moreover, we require for $n$ and $m$ to be co-prime only, and so we don't have to worry about whether any of the numbers $n, m$ is composite or not. The encryption and decryption processes are similar as those in the RSA. Hence, in this cryptosystem we may apply the above kind of numbers of arbitrary length being still sure that the system works well. The price for that is not so high: the size of a message $M$ (as a number) permitted by the new system must be smaller than log (in base 2) of $n\cdot m$. The proposed cryptosystem can be applied in the case the numbers $n,m$ are 'sufficiently large' for a user, or as a completion of the classical RSA if $m,n$ are probable primes but possibly not prime, or in a 'secret sharing'-type cryptosystem. The numbers $n,m$ can be also taken from a narrower class of probable primes to base 2 numbers, e.g., Euler, or strong, or Baillie-PSW.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
RSAPseudoprimes in base 2Carmichael numbers
Contact author(s)
mwojt @ ukw edu pl
History
2020-10-20: last of 6 revisions
2020-06-03: received
See all versions
Short URL
https://ia.cr/2020/624
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/624,
      author = {Marek Wójtowicz},
      title = {RSA for poor men: a cryptosystem based on probable primes to base 2 numbers},
      howpublished = {Cryptology ePrint Archive, Paper 2020/624},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/624}},
      url = {https://eprint.iacr.org/2020/624}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.