Expert answer:cryptosystem decrypt the message
Expert answer:Alice and Bob communicate using the Rabin public-key cryptosystem. They decide to use the “complete” Rabin system. Bob chooses an integer n= pq and an integer K Î Zn. He sends his public key (n, k) to Alice. Alice encrypts her digital message M and sends her encrypted message N to Bob. You are Bob. What are Alice’s four possible messages? P q n k 11 23 253 103Alice and Bob communicate using the RSA public-key cryptosystem. They decide to use “double encryption”. Bob chooses n= (p)(q) and two values of e, and sends his public key (n, e1, e2) to Alice. Alice encrypts a numerical message M, and sends the encrypted message N to Bob.You are Bob. Decrypt the message N pq e1 e2 2021 (43)(47) 527 389Alice and Bob communicate using the El Gamal public-key cryptosystem. Bob chooses (n, g, x) and sends his public key to Alice. Alice sends her encrypted message N to Bob. You are Bob. Decrypt the numerical message n g x 31 17 23
discrete_mathhw.docx
chapter_8.43___8.44___fermat_euler_theorem__public_key_crypt.docx
chapter_8.45__rabin.docx
chapter_8.46__rsa__el_gamal__ecc_2_.docx
Unformatted Attachment Preview
Discrete Math
Solve and Explain briefly
1. Alice and Bob communicate using the Rabin public-key cryptosystem. They decide to
use the “complete” Rabin system.
Bob chooses an integer n= pq and an integer K Zn. He sends his public key (n, k) to
Alice.
Alice encrypts her digital message M and sends her encrypted message N to Bob.
You are Bob. What are Alice’s four possible messages?
P
q
n
11
23
253
k
103
2. Alice and Bob communicate using the RSA public-key cryptosystem. They decide to use
“double encryption”. Bob chooses n= (p)(q) and two values of e, and sends his public key
(n, e1, e2) to Alice. Alice encrypts a numerical message M, and sends the encrypted
message N to Bob.
You are Bob. Decrypt the message
N
pq
2021
(43)(47)
e1
e2
527
389
3. Alice and Bob communicate using the El Gamal public-key cryptosystem. Bob chooses
(n, g, x) and sends his public key to Alice. Alice sends her encrypted message N to Bob.
You are Bob. Decrypt the numerical message
n
g
x
31
17
23
Section 8.43
Fermat/Euler Theorem
Understanding cryptology requires a little abstract algebra.
(covered in the omitted Sections 8.40 and 8.41)
A group, denoted ( ,∗),
is a set G paired with an operation ∗ defined on the set
such that
– the set G is closed under the operation ∗ .
– the operation ∗ is associative.
– the operation ∗ has exactly one identity element e in G .
– every element g in G has a unique inverse element h that is also in G.
Generally, the operation is assumed to be multiplication
and is omitted in the notation.
Note that ( ,⊗) = is not a group
because some elements are not invertible.
If we construct a subset of , denoted ∗ ,
containing only its invertible elements,
the elements that are relatively prime to ,
then ( ∗ , ⨂) is a group.
| ∗ | = ( )
Consider the multiplication table for ( ∗ , ⨂) .
Notice that every element appears once in each row and column of the table.
Every element has a unique inverse.
| ∗ | =
= ( )( )
( ) = ( − )( − ) =
And there is exactly one identity element, .
⊗ =
( ∗ , ⨂) is a finite group. Let ∈ ∗ .
Every element of ∗ is relatively prime to p.
Fermat’s Little Theorem
− ≡ ( )
, , , … , ( − ) ≡ , , , … , − ( )
⋅ ⋅ ⋅ … ⋅ ( − ) ≡ ⋅ ⋅ ⋅ … ⋅ − ( )
− ⋅ ( − )! ≡ ( − )! ( )
− ≡ ( )
Multiplying by a:
≡ ( )
Let ∈ ∗
≡ ( )
= ≡ ( )
= ≡ ( )
= ≡ ( )
= ≡ ( )
− = = ( )
= ≡ ( )
= ≡ ( )
= ≡ ( )
= ≡ ( )
Extending:
≡ ( )
≡ ( )
If ≡ ( ), then p is not a prime.
However, ≡ ( ) does not ensure that the number is a prime.
There are some composite numbers, called Carmichael Numbers,
for which ≡ ( ) for all ∈ .
The smallest Carmichael number is = ( )( )( ).
Fermat’s Little Theorem does not extend to non-prime values of n.
≡ ( )
Let ∈
= ≡ ( )
= ≡ ( )
= ≡ ( )
= ≡ ( )
= ≡ ( )
= ≡ ( )
= ≡ ( )
= ≡ ( )
Euler’s Theorem
Let n be a positive integer and let a be relatively prime to n.
( ) ≡ ( )
All the elements in ∗ are relatively prime to n by design.
But | ∗ | = ( )
∗
Therefore, for any element ∈ ∗ , | | ≡ ( ) .
Consider ∗ = { , , , , , }
( ) = − =
=
≡ ( )
= ≡ ( )
= ≡ ( )
=
≡ ( )
= ≡ ( )
= ≡ ( )
If p is a prime number, and a and p are relatively prime,
then ( ) = −
and
( ) = − ≡ ( )
( ) = − =
≡ ( )
Find the remainder when is divided by .
This is same as finding ( ).
Let = ; ( ) = − = .
≡ ( )
= ( )
÷ = .
. ( ) =
= ( ) +
( ) = ( )
≡ ( ) =
= ( )+ = ( ( ) )( ) ≡ [ ][ ( )] ≡ ( )
= ≡ ( ) = = ( )
= ( ) ≡ ( ) ( ) = ( ) ≡ ( )
= ( ) + ≡ ( )
= ( ) ≡ ( ) ( ) = ( ) ≡ ( )
= ( ) + ≡ ( )
Therefore, the remainder when is divided by is .
Section 8.44
Public Key Cryptography I
Private (secure) communication is possible in a public forum.
However, if the message is intercepted,
clever analysts can often determine the encoding process,
thereby potentially breaching the security of the system.
The key is to develop a system such that
revealing the encryption process (public key)
does not undermine the secrecy of the decryption process.
The process must be one that has a very difficult inverse.
It is relatively easy to do but very difficult to undo without “inside information”.
This type of process is called a “trapdoor” function.
The process of choice to date is “factoring”.
To date, there is no computationally efficient procedure for factoring positive integers.
While multiplying two large prime numbers may be tedious,
factoring the result is virtually impossible, even for computers.
The typical encryption process uses a number, = , of 4096 bits.
The encoded message should be conveyed by numbers, not words.
The standard system for converting (Roman) letters to numbers
is the 256-character ASCII code.
The three-digit “letters” are then combined into one very large number,
which must be smaller than the key size n .
Overview of the Encryption/Decryption Process
Public Cryptography II
Rabin’s Method
A simple public-key encryption system was developed by Michael Rabin in 1979.
In this system, a numerical message M is encrypted by squaring it mod n.
Decryption, then, requires finding the square roots of N, the encrypted message, in .
In general, this cannot be done for very large n without additional “inside” information,
because the process requires factoring n,
which is not practical, even for the fastest computer.
= , where p and q are primes, is called a “public-key”
because it can be revealed without compromising the security of the system.
For relatively small values of n, say up to 2500,
we can divide n by each prime up to √ to find a divisor.
Table of Primes
Factor .
√ = . … ≈
Trial division by the primes , , , , , , , , :
=
= ( )( )
In cryptology, large numbers with more than 1000 digits are the norm.
Trial division by the primes up to √ = is impractical,
even for the fastest computers.
The factors of a number that is the product of two primes, = ,
can be determined
if the number of invertible elements in , Euler’s totient, is known.
Suppose that = and ( ) = is known.
( ) = ( − )( − ) =
= =
=
( − ) (
− −
− −
− ) =
+ =
= −
− + =
=
±√ − ( )( )
= =
+
=
=
±√ −
=
= =
=
±√
−
=
=
±
=
= = ( )( ) =
For large values of n, we need computer assistance.
Factor
An integer factoring calculator is available (for up to 7 digit numbers) online :
www.calculatorsoup.com/calculators/math/factors.php
= ( )( )( )
Rabin’s method also requires finding square roots in .
This is not difficult for odd primes.
But to determine them in large composite numbers
which are themselves the products of two large primes ( = )
requires first factoring n, an extremely difficult process.
Square Roots Modulo n
Let n be a positive integer and let ∈ .
If there is an element ∈ such that = ⨂ = ,
we call the element a a “quadratic residue (mod n)”.
Otherwise, a is called a “quadratic non-residue”.
Consider .
= ( )
Notice that the quadratic residues are = , , , .
(“0” is a trivial quadratic residue and is usually not included.)
Note that the quadratic residues are symmetric.
= ( − ) ( ) = (− ) ( )
Square roots of quadratic residues are not unique; they come in pairs.
√ = ±
e.g., the two square roots of are and in .
These can be rewritten as ± ( ) or ± ( ) .
Note that these are the same two square roots
since ± ( ) ≡ ∓ ( ).
If p is a prime, then a quadratic residue in has at most two square roots.
If the modulus is an odd prime, is denoted by .
−
The number of quadratic residues, excluding 0, in is
.
Euler’s Criterion can be used
to determine which values of a are quadratic residues in .
−
−
−
=
=
={
−
( ),
− ( ), −
Find all quadratic residues in .
= ( ) =
= = ( ), { = ( ) =
= ( ) =
−
= ( ) = −
= = − ( ), { = ( ) = −
= ( ) = −
Find all solutions of ≡ ( )
−
−
=
=
= ( ) = ( ) ≡ ( ) = ( ) = − ( )
2 is not a quadratic residue in .
Therefore, there is no solution.
Quadratic residues in composite moduli can have multiple square roots.
Consider .
( )
Notice that the quadratic residues are = ( ), , , , , .
The four square roots of are , , , and in
These can be rewritten as ± ( ) and ± ( ).
If = , then a quadratic residue in , e.g., has at most four square roots,
two square roots from = and two square roots from = .
Consider .
( )
Consider .
( )
√ ( ) = ±
or ( ) and ( )
√ ( ) = ± , ±
or ( ) and ( )
The four square roots (mod 15) can be determined
by solving the four pairs of congruences simultaneously
with the Chinese Remainder Theorem.
− ( ) =
≡ ( )
≡ ( )
≡ ( )
− ( ) =
≡ ( )
≡ ( )
≡ ( )( )( ) + ( )( )( ) = ( )
≡ ( )
≡ ( )
≡ ( )
≡ ( )( )( ) + ( )( )( ) = ( )
≡ ( )
≡ ( )
≡ ( )
≡ ( )( )( ) + ( )( )( ) = ( )
≡ ( )
The four square roots of 4 in are , , , .
If you know the four square roots of in , where = ,
you can readily determine p and q.
Let = and let ∈ be a quadratic residue.
Suppose ∈ has four distinct square roots in :
± and ±
The only possible factors of = are { , , , }.
= and =
− = ( − )( + ) = ( ) =
Then, n must be a factor of either ( − ) or ( + ).
Since the roots are distinct, ≠ ± .
( − ) ≠ ( ) and ( + ) ≠ ( ).
Therefore, neither ( − ) nor ( + ) are multiples of n.
n is not a factor of ( − ) or ( + ) .
( − , ) ≠
If ( − , = ) = , neither p nor q could be a divisor of ( − ).
Since ( − )( + ) = = , then p and q would have to be factors of ( + ),
which is impossible since ( + ) is not a multiple of n.
This results in a contradiction:
1 is not the greatest common divisor of − and n.
( − , = ) ≠
Therefore, since = , the only other possible divisors of n are p and q.
Either ( − , ) = and ( + , ) =
or ( − , ) = , and ( + , ) =
Let = .
Suppose that the four square roots of in are known.
√ ( ) = ± ± .
Then,
( − , ) = ( , ) =
( + , ) = ( , ) =
The two factors of are and .
Conversely, if the factors p and q are known,
the square roots of a in = can be determined.
Let be a square root of n in .
⨂ = ( )
By design, = , where p and q are primes.
⨂ = ( )
Therefore, ≡ ±√ ( ) and ≡ ±√ ( )
∈ = has at most two square roots in
and at most two square roots in .
Knowing the square roots of a in and ,
we can find the square roots of a in by solving the system of congruences:
≡ ±√ ( )
≡ ±√ ( )
The only complication is that there are four possible pairs of congruences,
and four simultaneous solutions,
only one of which will decrypt the message.
To date, there is no computationally efficient procedure to find square roots in .
However, for some special types of primes a simple solution has been determined.
If ≡ ( ),
and ∈ is a quadratic residue,
the square roots of a in are [± ( + )/ ] .
If ≡ ( ),
and ∈ is a quadratic residue,
±
+
−
( ) ,
=
the square roots of a in are { − +
−
⋅ ( ) , = −
This covers most of the odd primes.
The others, such as 17, 41, 73, etc., are ≡ ( ).
However, an algorithm is required to find the square roots.
Let = and let = = ( )( ) = .
≡ ( � …
Purchase answer to see full
attachment
How it works
- Paste your instructions in the instructions box. You can also attach an instructions file
- Select the writer category, deadline, education level and review the instructions
- Make a payment for the order to be assignment to a writer
- Download the paper after the writer uploads it
Will the writer plagiarize my essay?
You will get a plagiarism-free paper and you can get an originality report upon request.
Is this service safe?
All the personal information is confidential and we have 100% safe payment methods. We also guarantee good grades