• Modulus operationmodTake over operations%

  • The original root:

    • A primal root is a mathematical symbol. Let’s saymIs a positive integer,aIs an integer, ifadiemThe order is equal to thePhi (m)Is said,aFor the mouldmA primitive root of(includingPhi (m)saidmEuler function of)
    • Let’s say I have a numbergisPThe primal root of thetag^i mod PThe results are different, and there are1<g<P.0<i<PWhat it comes down to isg^(P-1) = 1 (mod P)If and only if the exponent isP-1Is true when(herePIs a prime number)
    • In short,G ^ I mod p ≠ g^j mod p (pFor prime), includingI indicates jandi, jbetween1to(p-1)Between,gforpThe original root
    • Ex. :3^x mod 17 = yAt this time,3 < 17and17Is prime, thenxThe value of is1 ~ 16When, as a result,yAnd the range of1 ~ 16andx ! = y.3That is17The original root

  • The euler functionphi

    • Coprime: If two positive integers, except1If there are no other common divisor, then the two numbers are mutually prime
    • Find less than or equal tonAnd with thenA function of the number of mutualprimes, called the Euler function, expressed asPhi (n)
    • For example,Phi (8) = 4, i.e.,1 hc-positie.Phi (7) = 6, i.e.,6

  • Euler function characteristics

    • whennWhen it’s prime,φ n is equal to n minus 1
    • ifnCan be decomposed into the product of two mutually prime integers, such asn = A * B, then:φ A times B is equal to φ A times φ B.
    • According to the above two points: ifNIt’s two prime numbersP1andP2Product of, thenPhi of N is equal to phi of P1 times phi of P2 is equal to phi of P1 minus phi of P2 minus phi.

  • Euler’s theorem

    • If you have two positive integersmandnEach other is prime. Somtheφ n to the power minus 1Can benDivisible, that is,M ^φ(n) mod n ≡ 1
    • Fermat’s little theorem: a special case of Euler’s theorem if two positive integersmandnEach other is prime, andnIt’s also a prime number, soPhi (n)As a result ofn - 1, i.e.,M to the n minus 1 mod n ≡ 1

  • Formula translation

∵ ≡ 1 * 1 m ≡ 1 ^ k m ∴ m ^ phi mod n (n) ≡ 1 ∴ phi m ^ k * (n) ≡ 1 ∴ mod n phi m ^ k * (n + 1) mod n = m (equal on both sides are multiplied by the m)Copy the code

  • Die inverse element

    • If you have two positive integerseandxMutual prime, then you must find integersd,ed - 1bexDivisible. SodiseforxThe modulo inverse element of.
E times d mod x ≡ 1 e times d is kx plus 1 (Ed is a multiple of x plus 1) m to the Ed mod n ≡ mCopy the code
- Finally 'm ^ Ed mod n = m' (see 6. Formula translation, where ` e ` and ` phi (n), ` co-prime ` d ` is ` e ` relative to ` phi (n) ` module of the element) - features: as long as ` d ` is ` e ` relative to ` phi (n) ` mode against the elements, then ` m ` and ` n ` relationship can not co-prime, as long as ` m < n ` equation can be established.Copy the code

  • Diffie Hermann key exchange

    • M ^ Ed mod n ≡ mThe formula continues to be deduced (D is the modulo inverse of e with respect to φ(n))
    • –> m ^ e mod n = CThe encryption,e&nIs the public key
    • –> C ^ d mod n = mNamely,d&nIs the private key
    • In the same waym ^ d mod n = C C ^ e mod n = m, i.e.,e & dIt can be encrypted or decrypted.

  • Terminal Experience RSA

    • openssl genrsa -out private.pem 1024 Example Generate an RSA private key of 1024 bits
    • openssl rsa -in private.pem -pubout -out public.pem Extract the public key from the private key
    • openssl rsa -in private.pem -text -out private.txt Turn the private key into plain text for viewing
    • openssl rsautl -encrypt -in msg.txt -inkey public.pem -pubin -out encrypt.txt Use the public key to encrypt the msg.txt file to enctypt.txt
    • openssl rsautl -decrypt -in encrypt.txt -inkey private.pem -out decrypt.txt Decrypt encrypt. TXT to decrypt.txt using the private key

  • Generate a certificate

    • openssl req -new -key private.pem -out rsacert.csr Requesting a CSR Certificate
    • openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt Use the CSR to request the CRT certificate
    • openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt Exporting a P12 Certificate
    • openssl x509 -outform der -in rsacert.crt -out rsacert.der Exporting the DER Certificate
    • iOSCode implementationRSAEncryption and decryption,Der certificateIs the private key,p12Is the public key