RSA Encryption Algorithm

The RSA encryption algorithm is an asymmetric encryption algorithm. Application Scenarios:

Encryption features: relatively secure, low encryption efficiency, small encrypted data

The complete process of using RSA encryption algorithm is as follows:

  1. Generate the corresponding public and private keys
  2. Use algorithms to encrypt data
  3. Decrypt the encrypted data using the corresponding algorithm

1. Generate public and private keys

Several concepts are involved: Euler functions, modular inversions, let’s look at each one

The euler function

Concept: Given any positive integer n, find out how many positive integers less than or equal to n form a mutual relationship with n. The way in which ϕ(n)\phi (n)ϕ(n) ϕ(n) represents ϕ(n) as ϕ(8)=4\phi(8)=4ϕ(8)=4, and calculates the Euler function of 8, 1, 2, 3, 4, 5, 6, 7, 8, in which 1357 is essential, ϕ(7)=6\phi(7)=6ϕ(7)=6 1, 2, 3, 4, 5, 6 are all 6 in number.

Function characteristics

Die inverse

Concept: also known as modular inverse elements, if two positive integers e and x are mutually prime, then the integer D must be found, and yes Ed -1 is divisible by X. (e) ∗ d % x = 1 (e * d) \ % x = 1 (e) ∗ d % x = 1 e ∗ ∗ d = k + 1 e * d = k * x x + 1 e ∗ ∗ d = k + 1, x at this point d is e exactly the elements of x.

2. Encrypt the message

3. Decrypt the message

Process flow chartWhere: public key: N and E Private key: N and D Plaintext: m Ciphertext: m Description: 1.n Is a large integer, usually 1024 binary digits, 232 decimal bits, and 768 binary bits. 2. Because of the requirement
ϕ ( n ) \phi(n) The easiest way to do this is to multiply two prime numbers and get P1,p2,
ϕ ( n ) = ( p 1 – 1 ) ( p 2 – 1 ) \phi(n)=(p1-1)(p2-1) 3. By finally
ϕ ( n ) \phi(n) You get e and D, inverse elements according to the modulo above. RSA security: Except for the public key, n and E, the other four digits are not public. The method of decrypting RSA to obtain D is as follows: 1. And in order to solve for d, because of
e ∗ d = ϕ ( n ) ∗ k + 1 e*d=\phi(n)*k+1 . 2. E is known, but know
ϕ ( n ) \phi(n) Since n=p1*p2. This can only be done by factoring n.

Terminal Command Demo

OpenSSL is built into the Mac system, so we can play RSA directly with Minling.

The command meaning
genrsa Generate and enter an RSA private key
rsautl Use the RSA key to perform encryption, decryption, signature, and authentication operations
rsa Process RSA key format conversion and other issues
  • Generate an RSA key. The key length is 1024 bits.

  • Extract the public key from the private key

– The following files are generated

  • Converts the private key to clear text
  • Encrypt data with the public key and decrypt data with the private key

  • Encrypts data using a private key and decrypts data using a public key

Code implementation:

    1. Load the public key
    [[RSACryptor sharedRSACryptor] loadPublicKey:[[NSBundle mainBundle] pathForResource:@"rsacert.der" ofType:nil]];
    2. Load the private key
    [[RSACryptor sharedRSACryptor] loadPrivateKey: [[NSBundle mainBundle] pathForResource:@"p.p12" ofType:nil] password:@"123456"];
        NSData * result = [[RSACryptor sharedRSACryptor] encryptData:[@"hello" dataUsingEncoding:NSUTF8StringEncoding]];
        
    / / base64 encoding
    NSString * base64 = [result base64EncodedStringWithOptions:0];
    NSLog(@"After encryption :%@\n",base64);
    
    / / decryption
    NSData * dcStr = [[RSACryptor sharedRSACryptor] decryptData:result];
    NSLog(@"% @",[[NSString alloc] initWithData:dcStr encoding:NSUTF8StringEncoding]);
Copy the code