🏳️
The CTF Recipes
  • Introduction
  • Cryptography
    • Introduction
    • General knowledge
      • Encoding
        • Character encoding
          • ASCII
          • Unicode
          • UTF-8
        • Data encoding
          • Base16
          • Base32
          • Base64
      • Maths
        • Modular arithmetic
          • Greatest Common Divisor
          • Fermat's little theorem
          • Quadratic residues
          • Tonelli-Shanks
          • Chinese Remainder Theorem
          • Modular binomial
      • Padding
        • PKCS#7
    • Misc
      • XOR
    • Mono-alphabetic substitution
      • Index of coincidence
      • frequency analysis
      • Well known algorithms
        • 🔴Scytale
        • 🔴ROT
        • 🔴Polybe
        • 🔴Vigenere
        • 🔴Pigpen cipher
        • 🔴Affine cipher
    • Symmetric Cryptography
      • AES
        • Block Encryption procedure
          • Byte Substitution
          • Shift Row
          • Mix Column
          • Add Key
          • Key Expansion / Key Schedule
        • Mode of Operation
          • ECB
            • Block shuffling
              • Challenge example
            • ECB Oracle
              • Challenge example
          • CBC
            • Bit flipping
              • Challenge example
            • Padding oracle
              • Challenge example
          • OFB
            • Key stream reconstruction
            • Encrypt to Uncrypt
  • 🛠️Pwn
    • General knowledge
      • STACK
        • Variables storage
        • Stack frame
      • PLT and GOT
      • HEAP
        • HEAP operations
        • Chunk
        • Bins
        • Chunk allocation and reallocation
      • Syscall
    • Architectures
      • aarch32
        • Registers
        • Instruction set
        • Calling convention
      • aarch64
        • Registers
        • Instruction set
        • Calling convention
      • mips32
        • Registers
        • Instruction set
        • Calling convention
      • mips64
        • Registers
        • Instruction set
        • Calling convention
      • x86 / x64
        • Registers
        • Instruction set
        • Calling convention
    • Stack exploitation
      • Stack Buffer Overflow
        • Dangerous functions
          • gets
          • memcpy
          • sprintf
          • strcat
          • strcpy
        • Basics
          • Challenge example
        • Instruction pointer Overwrite
          • Challenge example
        • De Bruijn Sequences
        • Stack reading
          • Challenge example
      • Format string
        • Dangerous functions
          • printf
          • fprintf
        • Placeholder
        • Data Leak
          • Challenge example
        • Data modification
          • Challenge example
      • Arbitrary code execution
        • Shellcode
        • ret2reg
        • Code reuse attack
          • Ret2plt
          • Ret2dlresolve
          • GOT Overwrite
          • Ret2LibC
          • Leaking LibC
          • Ret2csu
          • Return Oriented Programming - ROP
          • Sigreturn Oriented Programming - SROP
          • Blind Return Oriented Programming - BROP
            • Challenge example
          • 🔴Call Oriented Programming - COP
          • 🔴Jump Oriented Programming - JOP
          • One gadget
        • Stack pivoting
    • 🛠️Heap exploitation
      • Heap overflow
        • Challenge example
      • Use after free
        • Challenge example
      • 🛠️Double free
      • 🔴Unlink exploit
    • Protections
      • Stack Canaries
      • No eXecute
      • PIE
      • ASLR
      • RELRO
    • Integer overflow
Powered by GitBook
On this page

Last updated 2 years ago

A modular binomial problem is a mathematical problem in which a binomial expression of the form :

where :

  • a and b are integers,

  • e is a positive integer (the exponent),

  • and N is a positive integer (the modulus).

In cryptography, the modular binomial problem is used in RSA encryption, where the integers a, b, and N are related to the encryption and decryption keys, and the exponent e is used to encrypt a message. Solving the modular binomial problem for a given c, e, and N is considered to be a hard problem and is the basis of RSA encryption's security.

Searching p and q

The modular binomial problem can have the following form :

Given the value of c1, c2 a1, a2, e1, e2 and N and where N = p*q it's possible to retrieve p and q as follow :

The main idea is to :

  • upper c1 using the exponent used in the c2 equation : e2

  • upper c2 using the exponent used in the c1 equation : e1

Doing that, c1 and c2 are on the same exponent : e1.e2

In order to retrieve q it's needed to isolate it, so it's needed to make the two equation to had the same p value

  • Multiply by a1**(-e1*e2) in the c1 equation reduce P factor to 1

  • Multiply by `a2**(-e1*e2) in the c2 equation reduce P factor to 1

Then, by substrat c1 to c2 there is a p**(e1*e2) - p**(e1*e2) which is 0 so they can be remove of the equation

Make the same with c2

Then

So, q = gcd(pow(a2,(-e2 * e1),N) * pow(c2, e1, N) - pow(a1, (-e1 * e2), N) * pow(c1, e2, N), N)

Do the same to get p

x=(a+b)e mod Nx = (a + b)^e \bmod Nx=(a+b)emodN
c1=(a1⋅p+b1⋅q)e1 mod Nc2=(a2⋅p+b2⋅q)e2 mod Nc_1 = (a_1 \cdot p + b_1 \cdot q)^{e_1} \bmod N\\ c_2 = (a_2 \cdot p + b_2 \cdot q)^{e_2} \bmod N\\c1​=(a1​⋅p+b1​⋅q)e1​modNc2​=(a2​⋅p+b2​⋅q)e2​modN
c1e2=(a1⋅p+b1⋅q)e1⋅e2 mod Nc1e2=(a1⋅p)e1⋅e2+(b1⋅q)e1⋅e2 mod Na1−e1⋅e2⋅c1e2=a1−e1⋅e2⋅(a1⋅p)e1⋅e2+a1−e1⋅e2⋅(b1⋅q)e1⋅e2 mod Na1−e1⋅e2⋅c1e2=pe1⋅e2+a1−e1⋅e2⋅(b1⋅q)e1⋅e2 mod Nc_1^{e_2} = (a_1 \cdot p + b_1 \cdot q)^{e_1 \cdot e_2} \bmod N\\ c_1^{e_2} = (a_1 \cdot p)^{e_1 \cdot e_2} + (b_1 \cdot q)^{e_1 \cdot e_2} \bmod N\\ a_1^{-e_1 \cdot e_2} \cdot c_1^{e_2} = a_1^{-e_1 \cdot e_2} \cdot (a_1 \cdot p)^{e_1 \cdot e_2} + a_1^{-e_1 \cdot e_2} \cdot (b_1 \cdot q)^{e_1 \cdot e_2} \bmod N\\ a_1^{-e_1 \cdot e_2} \cdot c_1^{e_2} = p^{e_1 \cdot e_2} + a_1^{-e_1 \cdot e_2} \cdot(b_1 \cdot q)^{e_1 \cdot e_2} \bmod N\\c1e2​​=(a1​⋅p+b1​⋅q)e1​⋅e2​modNc1e2​​=(a1​⋅p)e1​⋅e2​+(b1​⋅q)e1​⋅e2​modNa1−e1​⋅e2​​⋅c1e2​​=a1−e1​⋅e2​​⋅(a1​⋅p)e1​⋅e2​+a1−e1​⋅e2​​⋅(b1​⋅q)e1​⋅e2​modNa1−e1​⋅e2​​⋅c1e2​​=pe1​⋅e2​+a1−e1​⋅e2​​⋅(b1​⋅q)e1​⋅e2​modN
c2e1=(a2⋅p+b2⋅q)e2⋅e1 mod Nc2e1=(a2⋅p)e2⋅e1+(b2⋅q)e2⋅e1 mod Na2−e2⋅e1⋅c2e1=a2−e2⋅e1⋅(a2⋅p)e2⋅e1+a2−e2⋅e1⋅(b2⋅q)e2⋅e1 mod Na2−e2⋅e1⋅c2e1=pe2⋅e1+a2−e2⋅e1⋅(b2⋅q)e2⋅e1 mod Nc_2^{e_1} = (a_2 \cdot p + b_2 \cdot q)^{e_2 \cdot e_1} \bmod N\\ c_2^{e_1} = (a_2 \cdot p)^{e_2 \cdot e_1} + (b_2 \cdot q)^{e_2 \cdot e_1} \bmod N\\ a_2^{-e_2 \cdot e_1} \cdot c_2^{e_1} = a_2^{-e_2 \cdot e_1} \cdot (a_2 \cdot p)^{e_2 \cdot e_1} + a_2^{-e_2 \cdot e_1} \cdot (b_2 \cdot q)^{e_2 \cdot e_1} \bmod N\\ a_2^{-e_2 \cdot e_1} \cdot c_2^{e_1} = p^{e_2 \cdot e_1} + a_2^{-e_2 \cdot e_1} \cdot (b_2 \cdot q)^{e_2 \cdot e_1} \bmod N\\c2e1​​=(a2​⋅p+b2​⋅q)e2​⋅e1​modNc2e1​​=(a2​⋅p)e2​⋅e1​+(b2​⋅q)e2​⋅e1​modNa2−e2​⋅e1​​⋅c2e1​​=a2−e2​⋅e1​​⋅(a2​⋅p)e2​⋅e1​+a2−e2​⋅e1​​⋅(b2​⋅q)e2​⋅e1​modNa2−e2​⋅e1​​⋅c2e1​​=pe2​⋅e1​+a2−e2​⋅e1​​⋅(b2​⋅q)e2​⋅e1​modN
a2−e2⋅e1⋅c2e1−a1−e1⋅e2⋅c1e2=pe2⋅e1+a2−e2⋅e1⋅(b2⋅q)e2⋅e1−pe1⋅e2+a1−e1⋅e2⋅(b1⋅q)e1⋅e2 mod N=a2−e2⋅e1⋅(b2⋅q)e2⋅e1+a1−e1⋅e2⋅(b1⋅q)e1⋅e2 mod Na_2^{-e_2 \cdot e_1} \cdot c_2^{e_1} - a_1^{-e_1 \cdot e_2} \cdot c_1^{e_2} = p^{e_2 \cdot e_1} + a_2^{-e_2 \cdot e_1} \cdot (b_2 \cdot q)^{e_2 \cdot e_1} - p^{e_1 \cdot e_2} + a_1^{-e_1 \cdot e_2} \cdot(b_1 \cdot q)^{e_1 \cdot e_2} \bmod N \\= a_2^{-e_2 \cdot e_1} \cdot (b_2 \cdot q)^{e_2 \cdot e_1} + a_1^{-e_1 \cdot e_2} \cdot(b_1 \cdot q)^{e_1 \cdot e_2} \bmod Na2−e2​⋅e1​​⋅c2e1​​−a1−e1​⋅e2​​⋅c1e2​​=pe2​⋅e1​+a2−e2​⋅e1​​⋅(b2​⋅q)e2​⋅e1​−pe1​⋅e2​+a1−e1​⋅e2​​⋅(b1​⋅q)e1​⋅e2​modN=a2−e2​⋅e1​​⋅(b2​⋅q)e2​⋅e1​+a1−e1​⋅e2​​⋅(b1​⋅q)e1​⋅e2​modN
  1. Cryptography
  2. General knowledge
  3. Maths
  4. Modular arithmetic

Modular binomial

PreviousChinese Remainder TheoremNextPadding