Applications of Number Theory in Computer Science Curriculum

Applications of Number Theory in Computer Science Curriculum

Ciphertext Only Cryptanalytic Attack on MerkleHellman Knapsack: Dynamic Programming Algorithm Input: A={a1, a2, an} public key, S - ciphertext Output: The binary array B plaintext Algorithm: Let P[i, j] be TRUE if there is a subset of first i elements of A that sums to j, 0 i n , 0 j S Step 1: Computation of P P[0][0] TRUE for j = 1 to S do: P[0][j] FALSE for i = 1 to n do: for j = 0 to S do: if (j A[i] < 0): P[i][j] = P[i-1][j] else: P[i][j] = P[i-1][j-A[i]] or P[i-1][j] Step 2: Backtracking Let B be an array of n + 1 elements initialized to 0 i n, j S while i > 0: if (j A[i]) 0): if (P[i-1][j-A[i]] is True): B[i] B[i] + 1 j j A[i] ii1 else: i i 1 Output: array B, elements of B that equal to 1 construct a desired subset of A that sums to S EXAMPLE

Input: A={1, 4, 5, 2}, S =3 j=0 j=1 j=2 j=3 i=0 TRUE FALSE FALSE FALSE i=1 A[1] =1 TRUE TRUE FALSE FALSE i=2 A[2] = 4

TRUE TRUE FALSE FALSE i=3 A[3] = 5 TRUE TRUE FALSE FALSE i=4 A[4] = 2 TRUE TRUE TRUE TRUE Element is taken

Element is taken P[i-1][j-A[i]] or P[i-1][j] Merkle-Hellman Multiplicative Knapsack Cryptosystem Alice: Chooses set of relatively prime numbers P = {p1, pn} private (easy) knapsack Chooses prime M > p1* * pn Chooses primitive root b mod M Computes the public (hard) knapsack A = {a1, .an}, where ai is discrete logarithm of pi to base b: ai p b (mod M ) i 1 ai < M, such that:

Private Key: P, M, b Public Key: A Merkle-Hellman Multiplicative Knapsack Cryptosystem- Encryption Binary Plaintext T breaks up into sets of n elements long: T = {T1, Tk} n For each set Ti compute j 1 T ij a j C i Ci is the ciphertext that corresponds to plaintext Ti C = {C1, Ck) is ciphertext that corresponds to the plaintext T C is sent to Alice Merkle-Hellman Multiplicative

Knapsack Cryptosystem- Decryption For each Ci computes S i b C (mod M ) i Si is a subset product of the easy knapsack: n S i b Ci b Tij a j j 1 n b j 1 Tij a j n (b a j Tij ) j 1

Tij = 1 if and only if pj divides Si n j 1 Tij p j (mod M ) Merkle-Hellman Multiplicative Knapsack Example Easy (Private) Knapsack: P = {2, 3, 5, 7} M = 211, b = 17 Hard (Public) Knapsack: A= {19, 187, 198, 121} 2 1719(mod 211), 3 17187(mod 211), 5 17198(mod 211), 7 17121(mod 211) Plaintext: T = 1101 Ciphertext: C = 327 = 19 + 187 + 121 Decryption: S = 42 = 17327(mod 211) 42 = 21 * 31 *50 * 71 Plaintext: 1101

Recently Viewed Presentations

  • Slides: Chapter 2: Personality and Attitudes

    Slides: Chapter 2: Personality and Attitudes

    Times New Roman Arial Monotype Sorts Double Lines Understanding Individual Differences Concept of Personality Sources of Personality Differences Personality Structure: The "Big Five" Personality Factors* (Each factor is a continuum of many related traits) Personality and Behavior: Specific Personality Traits*...
  • Nuclear Magnetic Resonance Spectroscopy

    Nuclear Magnetic Resonance Spectroscopy

    Visible. In the mid 1660's, Sir Isaac Newton laid the foundation of spectroscopy by the discovery of the continuous spectrum of white light. The acceptance that light was comprised of seven colors led scientists on a journey to understand it's...
  • Live Healthy - Job Corps

    Live Healthy - Job Corps

    Live Healthy! campaign. Guidance for each staff member on center. ... much of the current debate has been fractious and etiologies of obesity have been attributed to eating behavior or fast food, personality issues, depression, addiction, or genetics. ... The...
  • LCAC Leadership PMS377 Program Managers  Washington, DC CAPT

    LCAC Leadership PMS377 Program Managers Washington, DC CAPT

    PMS377 Program Managers - Washington, DCCAPT Frank J. Reh, USN (Jul 66 to Jul 68) CAPT Roland F. Wilkinson, USN (July 68 to Sep 71) CAPT Cabell S. Davis, USN (Sep 71 to Apr 74) CAPT James W. Lisanby, USN...
  • Chemical property:

    Chemical property:

    When electricity is passed through molten salt, a gray metal forms at one terminal and a yellow-green gas at the other. physical. physical. physical. physical. chemical. chemical. chemical. Extensive Property Intensive Property Depends on the amount of matter in a...
  • Writers Workshop SLIDE 1 SLIDE 3 Table of

    Writers Workshop SLIDE 1 SLIDE 3 Table of

    Present the necessary backgroundto connect your hook and your thesis statement. The. Bridge. ties the hook to the . prompt . and . thesis statement . while providing the reader with background information. Introduction: Thesis Statement. Ittakes a stand rather...
  • Emerging Information Technologies: The Impact on Academic ...

    Emerging Information Technologies: The Impact on Academic ...

    Emerging Information Technologies: The Role of XML, DOIs, OpenURL, and Federated Search William H. Mischo [email protected] Grainger Engineering Library Information Center University of Illinois at Urbana-Champaign 2002 International Conference on Digital Archive Technologies (ICDAT2002) December 19, 2002
  • Operational Execution. Made Better. Objective The objective is

    Operational Execution. Made Better. Objective The objective is

    The objective is to track Mosaic's Super Chiller Mountain Beverage sales while monitoring the performance of the associated categories / sub-categories of packaged beverages. Data Category Definitions. Dispensed . Beverages: All Sizes . Cold Dispensed .