7 RSA Cryptosystem

RSA introduction

  RSA Cryptographic schemes are sometimes called Rivest-Shamir-Adleman Algorithm , It is currently the most widely used asymmetric cryptographic scheme .RSA stay USA( Except for other countries ) The duration of the patent lasts until 2000 year .

RSA Widely applied , But it is often used in practice :

• Encryption of small pieces of data , Especially for key transmission
• digital signature , such as Internet Digital certificate on .

   Be careful ：RSA Encryption is not intended to replace symmetric passwords , And it's better than things like AES Your password is much slower . This is mainly because RSA( Or other public key algorithms ) Many calculations are involved in the implementation . therefore , The main purpose of encryption features is to securely exchange keys of symmetric passwords ( Key transmission ). actually ,RSA Usually similar to AES Used together with symmetric passwords , Among them, the symmetric password is really used to encrypt a large amount of data .

RSA The underlying one-way function is the integer factorization problem : Multiplication of two large primes is very simple in calculation ( People can do it with pen and paper ), But it is very difficult to factorize the product result .

encryption and decryption

  RSA Both encryption and decryption are in the integer ring $Z_n$ To finish the , Modular computing plays a central role .
   Suppose you use RSA Encrypt plaintext $x$, And it means $x$ The bit string of is $Z_n=0,1,..,n-1$ Internal elements . So plaintext $x$ The binary value represented must be less than $n$. For ciphertext , This principle also holds . Encryption with public key and decryption with key can be expressed as :

RSA encryption ： Given public key $(n,e)=k_{pub}$ And plaintext $x$, Then the encryption function is ：$$y=e_{k_{pub}}(x)\equiv x^{e}modn\text{\hspace{1em}(1)}$$ among $x,y\in Z_n$

RSA Decrypt ： Given private key $d=k_{pr}$ And ciphertext $y$, Then the decryption function is ：$$x=d_{k_{pr}}(y)\equiv y^{d}modn\text{\hspace{1em}(2)}$$ among $x,y\in Z_n$

In the actual $x,y,n$ and $d$ Are very long numbers , Usually it is 1024 Bit or longer . value e Sometimes called crypto index or public index ; Private key d Sometimes called decryption index or secret index . If Alice I want to transmit an encrypted message to Bob, She needs to have Bob The public key (n,e), and Bob Will use his own private key d To decrypt . The next summary will discuss how to generate these three important parameters d,e and n. Now we can discuss RSA Some requirements of cryptosystem ;

1. Because the attacker can get the public key $(n,e)=k_{pub}$, therefore , For a given public key value $e$ and $n$, Determine private key $d$ In calculation
   It must be infeasible .
2. Due to plaintext $x$ It only depends on the modulus $n$ Size , So once RSA The number of bits encrypted cannot exceed $l$, among $l$ refer to $n$ Bit length of .
3. Calculation $x^{e}modn$( That is, encryption ) and $y^{d}modn$( Decryption ) It should be relatively simple . This means that we need a method that can quickly calculate the exponent of long integers .
4. Given a $n$ It should correspond to many keys / Public key for , otherwise , The attacker can launch a brute force attack ( The fact proved that , This requirement is easy to meet ).

Key generation and correctness verification

   A salient feature of all asymmetric schemes is , They all have a handshake stage to calculate the public key and private key . Key generation depends on the public key scheme , So it's very complicated . Here are RSA The steps involved in computing public and private keys in cryptosystems .

RSA Key generation ：

   Output ： Public key ：$k_{pub}$ = (n, e) And a private key ：$k_{pr}=(d)$

1. Choose two prime numbers $p$ and $q$.
2. Calculation $n=p\ast q$.
3. Calculation $\Phi (n)=(p-1)\ast (q-1)$.
4. Select the public index that meets the following conditions $e\in \{1,2,.....,\Phi (n)-1\}$: $$gcd(e,\Phi (n))=1.$$
5. Calculate the private key that meets the following conditions $d$: $$d\ast e\equiv 1mod\Phi (n)$$

   step 4 In the request $gcd(e,\Phi (n))=1$ It's to make sure that $e$ The existence module of the inverse element of $\Phi (n)$, So the private key $d$ Always there .
   There are two important parts in key generation : Step of selecting two large primes 1 And the steps of calculating the public and private keys 4 and 5. step 1 The generation of prime numbers in is very complex . Using the extended Euclidean algorithm (EEA) The key can be calculated immediately $d$ and $e$. In the actual , People usually start with $0<e<\Phi (n)$ Select a public parameter in the range , And $e$ The value of must meet the condition $gcd(e,\Phi (n))=1$. The input parameter $n$ and $e$ For Euclidean algorithm (EEA) You can get the following relationship :$$gcd(\Phi (n),e)=s\cdot \Phi (n)+t\cdot e$$
   If $gcd(\Phi (n),e)=1$, be $e$ Is a valid public key . Parameters obtained by using the extended Euclidean algorithm $t$ That is to say $e$ Inverse element , So there is :$$d=tmod\Phi (n).$$

Example ：Alice Want to send an encrypted message to Bob. First ,Bob Execution steps 1～5 Calculation RSA Parameters , And send his public key to Alice. Alice Then send the message (x=4) encryption , And will get the ciphertext y Send to Bob. Last ,Bob Decrypt with his own private key y.
Be careful ： Both private key index and public key index meet the conditions $e\ast d=3\ast 7\equiv 1mod\Phi (n)$

   In practice RSA The parameters will be very, very large RSA modulus n Should be at least 1024 Bit length , This makes p and q The bit length of is at least 512. Here is the bit length 1024 Of RSA Examples of parameters .
$$p=EODFD2C2.A288ACEBC705EFAB30E4447541A8C5447A37185CSA9CB98389CE4DE19199AA3069B404FD98C801568CB9170EB712BF10B4955CE9C9DC8CE6855C6123_h$$
$$q=EBEOFCF21866FD9A9FOD72F7994875A8D92E67AEE4B515136B2A778A8048B149828AEA30BDOBA34B977982A3D42168F594CA99F3981DDABFAB2369F229640115_h$$
$$n=CF33188211FDF6052BDBB1A37235EOABB5978A45C71FD381491AD12FC76DA0544C47568AC83D855D47CA8D8A779579AB72E635DOB0AAAC22D28341E998E90F82122A2C06090F43A37E0203C2B72E401FD06890EC8EAD4F07E686E906FO1B2468AE7B30CBD670255C1FEDE1A2762CF4392C0759499CCOABECFF008728D9A11AD{F}_h$$
$$e=40B028E1E4CCF07537643101FF72444AOBE1D7682F1EDB553E3AB4F6DD8293CA1945DB12D796AE9244D60565C2EB692A89B8881D58D278562ED60066DD8211E67315CF89857167206120405BO8B54D10D4EC4ED4253C75FA74098FE3F7FB751FF5121353C554391E114C85B5649725E9BD5685D6C9CTEED8EE442366353DC39,d=C21A93EE75148D4FBFD77285D79D6768C58EBF283743D2889A395F266C78F4A28E86F545960C2CEO1EB8AD5246905163B28DOB8BAABB959CC03F4EC499186168AE9ED6D88058898907E61CTcCCC584D65D801CFE32DFC983707F87F5AA6AE4B9E77B9CE630E2CODF05841B5E4984D059435D7270D500514891F7B77B804BED81_h$$

Verification of correctness :

RSA The core ：$$d_{k_{pr}}(y)=d_{k_{pr}}(e_{k_{pub}}(x))\equiv {x^e}^d\equiv x^{de}\equiv xmodn\text{\hspace{1em}(3)}$$ Let's prove that RSA The reason why the scheme is feasible .

prove ： It needs to be proved that decryption is the inverse function of encryption , namely $d_{k_{pr}}(e_{k_{pub}}(x))=x$. First, let's explain the construction rules of public key and private key : $d\ast e\equiv 1mod\Phi (n)$. Using the definition of modulo operator , This expression is equivalent to : $$d\ast e\equiv 1+t\ast \Phi (n)$$
   among t Is an integer . Bring this expression into the equation $(3)$ Available in :$$d_{k_{pr}}(y)\equiv x^{de}\equiv x^{1+t\ast \Phi (n)}\equiv x^{t\ast \Phi (n)}\ast x^1\equiv (x^{\Phi (n)}{)}^t\ast xmodn\text{\hspace{1em}(4)}$$
   That means we need to prove $x\equiv (x^{\Phi (n)}{)}^t\ast xmodn$. According to Euler's theorem , I.e $gcd(x,n)=1$, Then there are $1\equiv x^{\Phi (n)}modn$, Get a small promotion immediately :$$1\equiv 1^t\equiv (x^{\Phi (n)}{)}^{t}modn\text{\hspace{1em}(5)}$$

   among ,t For any integer . This proof process is discussed in two cases :

Case one : $gcd(x,n)=1$

In this case, Euler's theorem holds , The equation $5$ Insert $4$, obtain :$$d_{k_{pr}}\equiv (x^{\Phi (n)}{)}^t\ast x\equiv 1\ast x\equiv xmodn.ProveBI$$
   This part of the proof shows , To and RSA modulus $n$ Plaintext value of Coprime $x$ for , The decryption function is indeed the inverse of the encryption function .

The second case : $gcd(x,n)=gcd(x,p\cdot q)\ne 1$

   because $p$ and $q$ They are all prime numbers , You must have any of the following factors :$$x=r\ast porpersonx=s\ast q$$
   among $r,s$ All are integers , And meet $r<qands<p$. In order not to lose generality , hypothesis $x=r\cdot p$, Then you can get $gcd(x,q)=1$. The following form of Euler's theorem still holds :$$1\equiv 1^t\equiv (x^{\Phi (q)}{)}^{t}modq$$
   among t For any positive integer . Let's see next $(x^{\Phi (n)}{)}^t$: $$(x^{\Phi (n)}{)}^t\equiv (x^{(p-1)(q-1)}{)}^t\equiv ((x^{\Phi (q)}{)}^t{)}^{p-1}\equiv 1^{p-1}=1modq.$$
   Use the definition of modulo operators , This expression is equivalent to :$$(x^{\Phi (n)}{)}^t=1+u\ast q,$$
   among ,$u$ Is any integer . Multiply this equation by $x$ Available :$$x\ast (x^{\Phi (n)}{)}^t=x+x\ast u\ast q=x+(r\ast p)\ast u\ast q=x+r\ast u\ast (p\ast q)=x+r\ast u\ast n$$
$$namelyx\ast (x^{\Phi (n)}{)}^t=xmodn\text{\hspace{1em}(6)}$$

Put the equation $6$ Put it into the equation $4$ You can get the desired result :$$d_{k_{pr}}=(x^{\Phi (n)}{)}^t\ast x\equiv xmodn.ProveBI$$

Reference material ：《 In simple terms, cryptography 》–Christof Paar,Jan Pelzl Writing