Crypto and Number Toolkit

Modular arithmetic, Euclidean algorithms, number theory tools, cipher helpers

1. Modular arithmetic

Basic modular arithmetic
Result

                                            

                                                Example: −55 ≡ 7 (mod 31)
                                                

                                                    a = −55, n = 31.

                                                    −55 = −2·31 + 7.

                                                    Số dư là 7 nên: −55 ≡ 7 (mod 31).

                                                    Nhập a = -55, b = 0, n = 31 để xem a mod n = 7.
                                                

                                            

                                            

                                                Dùng để ôn cộng, trừ, nhân mod n, kể cả với số âm.
                                            

                                        

                                    

                                

                            


                            
                            

                                

                                    

                                        
Bitwise XOR

                                        

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            

                                                
                                                

                                                    

                                                        
                                                        
                                                    

                                                    

                                                        
                                                        
                                                    

                                                

                                            

                                            
                                        

                                        

                                            
Result

                                            

                                            

                                                Example: 1011 XOR 1100
                                                

                                                    Chọn Binary.

                                                    A = 1011, B = 1100.

                                                    1 xor 1 = 0, 0 xor 1 = 1, 1 xor 0 = 1, 1 xor 0 = 1.

                                                    Kết quả 0111 tương đương 7.
                                                

                                            

                                            

                                                Dùng cho stream cipher, One Time Pad, AddRoundKey của AES.
                                            

                                        

                                    

                                

                            


                            
                            

                                

                                    

                                        
Vigenere cipher

                                        

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            

                                                
                                                

                                                    

                                                        
                                                        
                                                    

                                                    

                                                        
                                                        
                                                    

                                                

                                            

                                            
                                        

                                        

                                            
Result

                                            

                                            

                                                Example: HELLO with key CAT
                                                

                                                    H=7, E=4, L=11, O=14; C=2, A=0, T=19.

                                                    Key repeats: CATCA.

                                                    H+C=9→J, E+A=4→E, L+T=30≡4→E, L+C=13→N, O+A=14→O.

                                                    Result: JEENO.
                                                

                                            

                                            

                                                Shift mod 26 by repeating key, use with Alphabet converter.
                                            

                                        

                                    

                                

                            

                        


                        
                        
2. Euclidean algorithms and fast exponentiation

                        


                            
                            

                                

                                    

                                        
GCD and inverse

                                        

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            
Result

                                            

                                            

                                                Example: gcd(30,18) and 7⁻¹ mod 26
                                                

                                                    GCD: 30 = 1·18+12, 18 = 1·12+6, 12 = 2·6+0.

                                                    gcd(30,18) = 6.

                                                    Inverse: 7·15 = 105 ≡ 1 (mod 26) so 7⁻¹ ≡ 15.
                                                

                                            

                                            

                                                Used for Affine, RSA, Diffie Hellman.
                                            

                                        

                                    

                                

                            


                            
                            

                                

                                    

                                        
Fast modular exponentiation

                                        

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            
Fast exponentiation

                                            

                                            
Direct BigInt

                                            

                                            

                                                Example: 3⁴⁹ mod 11
                                                

                                                    49 = 32+16+1. Binary square-and-multiply.

                                                    Result: 3⁴⁹ mod 11 = 1.
                                                

                                            

                                            

                                                Used for RSA, Diffie Hellman, ElGamal.
                                            

                                        

                                    

                                

                            


                            
                            

                                

                                    

                                        
Order modulo n

                                        

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            
Result

                                            

                                            

                                                Example: ord₁₀₀(7)
                                                

                                                    gcd(7,100)=1 so order exists.

                                                    7¹≡7, 7²≡49, 7³≡43, 7⁴≡1 (mod 100).

                                                    ord₁₀₀(7) = 4.
                                                

                                            

                                        

                                    

                                

                            

                        


                        
                        
3. Number theory tools

                        


                            
                            

                                

                                    

                                        
Euler phi and Euler theorem

                                        

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            
Result

                                            

                                            

                                                Example: φ(33), Euler and Fermat's little
                                                

                                                    33 = 3·11 so φ(33) = 20.

                                                    2²⁰ mod 33 = 1.

                                                    Fermat: 2³⁰ ≡ 1 (mod 31).
                                                

                                            

                                            

                                                Used for RSA key generation and large exponent reduction.
                                            

                                        

                                    

                                

                            


                            
                            

                                

                                    

                                        
Primitive root modulo p

                                        

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            
Result

                                            

                                            

                                                Example: is 3 a generator mod 31?
                                                

                                                    p=31, p−1=30 = 2·3·5.

                                                    Check 3¹⁵ mod 31 ≠ 1, 3¹⁰ mod 31 ≠ 1, 3⁶ mod 31 ≠ 1.

                                                    All pass → 3 is a generator.
                                                

                                            

                                            

                                                Useful for Diffie Hellman, ElGamal.
                                            

                                        

                                    

                                

                            


                            
                            

                                

                                    

                                        
Diffie Hellman shared key

                                        

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            
Result

                                            

                                            

                                                Example: p=31, g=3, x=5, y=7
                                                

                                                    A = 3⁵ ≡ 26 (mod 31).

                                                    B = 3⁷ ≡ 17 (mod 31).

                                                    K = 17⁵ ≡ 26⁷ ≡ 26 (mod 31).
                                                

                                            

                                            

                                                Brute-force discrete log for small p, then computes shared K.
                                            

                                        

                                    

                                

                            

                        


                        
                        
4. Converters and helpers

                        


                            
                            

                                

                                    

                                        
Alphabet converter

                                        

                                            
Letters to numbers

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                        

                                            Example: HELLO → 7 4 11 11 14
                                            

                                                H=7, E=4, L=11, L=11, O=14.
                                            

                                        

                                        

                                        

                                            
Numbers to letters

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            

                                            

                                                Example: 19 7 4 → THE
                                                
19→T, 7→H, 4→E.

                                            

                                        

                                    

                                

                            


                            
                            

                                

                                    

                                        
Decimal and binary

                                        

                                            
Decimal to binary

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                        

                                            Example: 13 → 1101₂
                                            
13 = 8+4+1 = 2³+2²+2⁰ → 1101.

                                        

                                        

                                        

                                            
Binary to decimal

                                            

                                                
                                                
                                            

                                            
                                        

                                        

                                            

                                            

                                                Example: 1010₂ → 10
                                                
1·8 + 0·4 + 1·2 + 0·1 = 10.

                                            

                                        

                                    

                                

                            


                            
                            

                                

                                    

                                        
Cipher cheat sheet

                                        

                                            
Affine: C = (a·P + b) mod n. Need a⁻¹ mod n.

                                            
Vigenere: shift mod 26 by key. Use Vigenere + Alphabet converter.

                                            
AES: XOR, matrix multiply in GF(2⁸), inverse in GF(2⁸).

                                            
RSA: C = Mᵉ mod n, M = Cᵈ mod n. Need extended Euclid, φ(n), fast exp.

                                            
Diffie Hellman: K = g^{ab} mod p. Need primitive root, fast exp.

                                            
Miller Rabin: check non-trivial square root of x² ≡ 1 mod n.

                                            

                                                Example: solve small RSA
                                                

                                                    1. Compute φ(n).

                                                    2. Choose e with gcd(e, φ(n))=1.

                                                    3. Find d = e⁻¹ mod φ(n).

                                                    4. Encrypt/decrypt with fast exp.
                                                

                                            

                                            

                                                Tip: master extended Euclid and fast exponentiation first.