RSA: cryptographic calculations
--------------------------------------------------------
The Chinese remainder theorem speeds up the decryption calculations of the RSA method, an asymmetric cryptographic method in which the encryption key and the decryption key are distinct. It is widely used on the Internet for authentication and the exchange of symmetric keys, as well as in bank cards. It relies on prime numbers and modular arithmetic.
The method involves choosing two prime numbers p and q, such as 101 and 113, and forming their product n, here 11,413 (in practice, much larger numbers are used so that factoring n is impossible with known methods). We then consider the product (p – 1)(q – 1), here 11,200, then a and b such that ab is equal to 1 modulo (p – 1)(q – 1). In our particular case, 6,597 and 3,533 work. Encrypting a number x between 0 and n – 1 then means calculating *x b modulo n; decrypting the same number means calculating x a modulo n*.
