[go: up one dir, main page]
Scribd
Upload
138 views6 pages

Mathematical Hard Problems in Cryptography

The document discusses several hard mathematical problems in cryptography including the discrete log problem, prime factorization problem, and decoding problem in code-based cryptography. These hard problems form the basis for cryptographic algorithms like Diffie-Hellman key exchange, RSA, and the McEliece cryptosystem.

Uploaded by

ashodhiya14
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
138 views6 pages

Mathematical Hard Problems in Cryptography

The document discusses several hard mathematical problems in cryptography including the discrete log problem, prime factorization problem, and decoding problem in code-based cryptography. These hard problems form the basis for cryptographic algorithms like Diffie-Hellman key exchange, RSA, and the McEliece cryptosystem.

Uploaded by

ashodhiya14
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Mathematical Hard Problem in

Cryptography

Sandeep Kumar
Application No. – 2003610
Roll No. - 3702362
Cryptography : Basic Setting
c
Alice Insecure Channel Bob
Adversary
c = Encryption(m) m = Decryption(c)
Goals of Cryptography:

 Confidentiality: Adversary can not learn anything about message.

 Integrity: Adversary can not modify the content of the message.

 Authenticity : Receiver (Bob) should be ascertain about the sender (Alice).

 Accountability: Sender (Alice) can not deny about a message that he has sent.
Discrete Log Problem(Hard Problem):

Let G = <g> be a cyclic group of large order. Given h = ga, it is hard to find a.

Diffee Hellman Key Exchange


Public Parameters:
Alice A cyclic group G = (Zp)*= <g> Bob
Where p is a large prime.

Alice send ga
Choose secret a ga
Bob Send gb
gb Choose secret b

From ga and gb , Adversary

Alice calculates (gb)a = gab


can not calcualte gab Bob calculates (ga)b = gab
Prime Factorization Problem(Hard Problem):
Given n = p.q (p and q are large primes), it is difficult to get p and q.

RSA Cryptosystem
Parameters:
Choose two large primes p and q and set n = p.q
Choose e, such that gcd(e, ϕ(n)) = 1.
Alice Choose d, such that d.e ≡ 1 mod (ϕ(n)).
Public Key: (e, n)
Private key (d, p, q)

On receiving c, Alice calculates: c = me mod(n) Bob

cd mod(n) = med mod(n) = m


Message m
Code Based Cryptography (Post Quantum Secure):
Binary Linear Block Code:
A linear block code C, of length n and dimension k, is a k dimensional subspace of .
Equivalently C can be defined through a generator matrix {G}k*n, as:
C = {m.G| m ϵ }

Parity Check matrix: The matrix {H}(n-k)*n ,such that G.HT = 0.


Syndrome: The syndrome of e ϵ , is given by s = e.HT.

Decoding Problem (Hard Problem):

Given s, H and w (small integer), it is hard to find e of weight w, such that


s = e.HT
McEleice Cryptosystem (1978):

Parameters:
Public Key: Generator Matrix : {G}k*n
t, error correcting capacity
Alice
Private key: A trapdoor, generally a parity check matrix H

On receiving c, c = m.G + e
Bob
Alice apply the decoding algorithm
weight of e is t
using trapdoor, to recover m
Message m

Thank You

You might also like