Welcome to the iOS Reverse series.

  • IOS reverse RSA theory
  • IOS reverse hash theory
  • IOS reverse application re-signature + wechat re-signature combat
  • IOS reverse Shell script + script re-signature
  • IOS reverse code injection +Hook
  • IOS reverse MachO file
  • IOS reverse dyLD process
  • IOS reverse HOOK principle of Fishhook
  • IOS reverse LLDB debugging

Writing in the front

This article will understand and use RSA encryption from three aspects: RSA theory, RSA terminal operation and RSA code operation. Sections one to four are the theoretical part. If you feel bored, you can skip to section five

Math class

  1. Prime number: a natural number greater than 1 that has no other factors except 1 and itself, such as 2,3,5,7
  2. Factor: Also called divisor. If the quotient of the integer a divided by the integer B (b≠0) is exactly an integer, then B is a factor of A. For example, 2 is a divisor of 4
  3. Mutuality: Two positive integers are mutuality if they have no common factors other than 1, such as 7 and 9 mutuality
  4. Mod operation: also called clock operation, slightly different from the usual mod operation. In RSA operation, the result is the same. Mod symbol is mod, mod symbol is %
  5. Congruence theorem: power operation property: if, then

The development history of cryptography

  1. Early days: useThis password(A list of Roman letters and numbers)
  2. Before 1976:Symmetric encryption algorithmEncryption and decryption use the same rule (key), the protection of this rule is extremely important, once leaked or Po solution, all information can be decrypted out
  3. In 1976:Difehermann key exchange algorithmIs by the United States two computer scientists Diffie (W.Diffie), Herman (M. Helman) jointly put forward the idea, can not directly transfer the key under the condition of key exchange
  4. In 1977:RSA encryptionOn the market. RSA was proposed and named after mathematicians Ron Rivest, Adi Shamir and Leonard Adleman at the Massachusetts Institute of Technology

2. The mathematics of RSA

  1. The original root:(p = prime), where I ≠j and I, j is between 1 and (p-1), then g is the root of p. Mod17 has different values, so 3 is the original root of 17

  2. Euler function: The number of numbers that are mutually compatible with n in numbers less than the positive integer n

Features:

  • if, and A and B are mutually quality, then
  • When n is prime, φ (n) = n-1, for example, φ (17) = 16
  1. Euler’s theorem: if two positive integers m and n are mutually prime, then m to the phi (n) minus 1 is divisible by n

Condition: M and N mutually

Formula:

  1. Fermat’s little theorem: is a special case of Euler’s theorem, when n itself is prime, φ (n) = n-1

Conditions: m and n are mutually prime, and N is prime

Formula:

  1. Modular antielement: If two positive integers e and x are mutually prime, then the integer D must be found such that Ed -1 is divisible by x, and D is called the modular antielement of e with respect to X

Condition: E and X are interchangeable

Formula:

  1. Euler function and formula derivation of modular antielements

Next, we use the known mathematical formula to deduce the formula:

① In euler’s theorem formula,If you raise both sides to the k power, you get that from the power properties of the same covariance theorem

② Then multiply both sides of the equation by m, and you get

③ In the formula of modular inverse elements,To get rid ofmodOperator. Now that the eD minus 1 is divisible by x, so eD has to be some k multiple of x plus 1

In the case of x=φ(n),

Conclusion: Euler functions and modular inverse elements can derive precursors to RSA encryption, and according to many calculations, it is found that the necessary conditions satisfied are not consistent with Euler functions

Condition:

  1. M < n.
  2. D is the modulo antielement of e with respect to φ(n);

Formula:

Mathematicians spent a lot of time and energy did not think of a way to continue to split the formula, until the emergence of Dufey and Hermann to solve the problem, and Dufey Hermann key exchange also opened a new direction of cryptography

Difehermann key exchange

  1. The server generates a random number 15 and then follows a fixed algorithmYou get encryptedInformation of 6Send to the client
  2. The client simultaneously generates a random number 13, according to the same algorithmgetInformation on 12Sending server
  3. The server and client can obtain the real information sent by the other side by calculating the information according to the original algorithm. The exchange of information does not involve the exchange of keys

Note:

  1. Information can only be intercepted by a third party during transmissionInformation of 6andInformation on 12“Does not capture the real information
  2. The rules of the algorithm are known to each other, and even if the algorithm is leaked, given that 3 to the n mod 17 is equal to 12, it’s not easy to figure out what n is

In fact, Defhelman’s purpose was to make the key exchange more secure, and then the THREE RSA brothers stepped in

The birth of RSA

Defhelman has succeededSplit intoand“, but did not put forward the idea

  1. RSA encryption algorithm:Decryption algorithm:M is plaintext, C is ciphertext, N and E are public keys, and n and D are private keys. ② D is the modular inverse element of e with respect to φ(n)
  2. RSA explain
    1. N Is large and contains 1024 bits
    2. Since we need to find φ(n), according to the characteristics of the Euclide function, the simplest way n is multiplied by two prime numbers: p1 and p2
    3. Finally, e and D are obtained from φ(n), generating 6 numbers in total: P1, P2, n, φ(n), e, and D
    4. Except for the n and e used in the public key, the other four numbers are not public
  3. RSA Security
    1. If you want Po to solve RSA, you get D, becauseE and φ (n).
    2. To get φ(n) we must know the primes P1 and p2
    3. Due to theAnd you have to factor n to figure it out
  4. The characteristics of RSA
    1. A relatively safe
    2. Low encryption efficiency
    3. Small encrypted data (generally used to encrypt Hash values for symmetric encryption)

5. Use the RSA terminal

  1. Generate the private keyopenssl genrsa -out private.pem 1024
  2. Extract the public key from the private keyopenssl rsa -in private.pem -pubout -out public.pem
  3. Look at the public keycat public.pem
  4. Convert the private key to a text fileopenssl rsa -in private.pem -text -out private.txt
  5. Encrypt with public keyopenssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
  6. Decrypt with a private keyopenssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
  7. Sign with a private keyopenssl rsautl -sign -in message.txt -inkey private.pem -out enc.bin
  8. Authentication with public keyopenssl rsautl -verify -in enc.bin -inkey public.pem -pubin -out dec.txt
  9. Viewing binariesxxd enc.bin

Vi. Certificate generation

  1. Generate request certificate file, need to fill in the country, province, organization name key string can also request a certificate from the certificate authorityopenssl req -new -key private.pem -out rsacert.csr
  2. Certificate signingopenssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt
  3. To generate a public keyopenssl x509 -outform der -in rsacert.crt -out rsacert.der
  4. Generate the private keyopenssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt

7. Base64 encoding

Base64 can encode any binary data and encode it into A text file composed of 65 characters, which is A performance of binary data. Base64 encoding is composed of (A-Z, A-Z, 0-9, + / =), at least 24 character bits, from left to right for A group of 6, less than 6 will fill zero. Use equal sign to fill the final blank, such as A binary is 01000001, fill 24 bits is 010000 010000 000000 000000, converted into base64 code is QQ==

  1. Terminal codingbase64 xxx.jpeg -o xxx.text
  2. Terminal decodingbase64 xxx.text -o xxx.jpeg -D
  3. Code coding
// Encode a character
- (NSString *)base64Endcode:(NSString *)str {
	NSData *data = [str dataUsingEncoding:NSUTF8StringEncoding];
	return [data base64EncodedStringWithOptions:0];
}
Copy the code
  1. Code decoding
// Decrypt a code
- (NSString *)base64Decode:(NSString *)str {
	NSData *data = [[NSData alloc] initWithBase64EncodedString:str options:0];
	return [[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding];
}
Copy the code

Write in the back

Knowledge of RSA and related coding is useful for reverse learning and is used in many places