Applications Of Mathematics 6p1v4h
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report l4457
Overview 6h3y3j
& View Applications Of Mathematics as PDF for free.
More details h6z72
- Words: 3,749
- Pages: 35
Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography
Applications of Mathematics
Crytanalysis Classical Cryptography The RSA Cryptosystem
Dr. Ramdas B. Sonawane Ness Wadia College of Commerce, Pune
RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Cryptography I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis
The subject of transforming information so that it cannot be easily recovered without special knowledge. Inventing cipher systems; protecting communications and storage.
Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Cryptography II Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
The earliest known of cryptography was by Julius Caesar. He made messages secret by shifting each letter three letters forward in the alphabet. For instance, using this scheme the letter B is sent to E and the letter X is sent to A. This is an example of encryption, that is, the process of making a message secret. Caesar’s encryption method can be represented by the function f that assigns to the nonnegative integer p, p ≤ 25, the integer f (p) in the set {0, 1, 2, · · · , 25} with f (p) = (p + 3) mod 26. Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography II Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography
In the encrypted version of the message, the letter represented by p is replaced with the letter represented by (p + 3) mod 26.
The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography III Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Example 1. What is the secret message produced from the message “MEET YOU IN THE PARK” using the Caesar cipher? solution First replace the letters in the message with numbers. This produces 12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10. Now replace each of these numbers p by f (p) = (p + 3) mod 26. This gives 15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13. Translating this back to letters produces the encrypted message “PHHW BRX LQ WKH SDUN.” Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography IV Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
To recover the original message from a secret message encrypted by the Caesar cipher, the function f −1 , the inverse of f , is used. Note that the function f −1 sends an integer p from Z26 , to f −1 (p) = (p − 3) mod 26. i.e. to find the original message, each letter is shifted back three letters in the alphabet, with the first three letters sent to the last three letters of the alphabet. The process of determining the original message from the encrypted message is called decryption. There are various ways to generalize the Caesar cipher. For example, instead of shifting the numerical equivalent of Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography V Applications of Mathematics Dr. Ramdas B. Sonawane
each letter by 3, we can shift the numerical equivalent of each letter by k, so that
Cryptography Classical Cryptography
f (p) = (p + k)
mod 26.
Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption
Such a cipher is called a shift cipher. Note that decryption can be carried out using f −1 (p) = (p − k) mod 26.
RSA Decryption Portfolio Problem
Here the integer k is called a key.
Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography VI Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Example 2. Encrypt the plaintext message “STOP GLOBAL WARMING” using the shift cipher with shift k = 11. solution To encrypt the message “STOP GLOBAL WARMING” we first translate each letter to the corresponding element of Z26 . This produces the string 18 19 14 15 6 11 14 1 0 11 22 0 17 12 8 13 6. We now apply the shift f (p) = (p + 11) mod 26 to each number in this string. We obtain 3 4 25 0 17 22 25 12 11 22 7 11 2 23 19 24 17. Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography VII Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Translating this last string back to letters, we obtain the ciphertext “DEZA RWZMLW HLCXTYR.” Example 3. Decrypt the ciphertext message “LEWLYPLUJL PZ H NYLHA ALHJOLY” that was encrypted with the shift cipher with shift k = 7. solution To decrypt the ciphertext “LEWLYPLUJL PZ H NYLHA ALHJOLY” we first translate the letters back to elements of Z26 . We obtain 11 4 22 11 24 15 11 20 9 11 15 25 7 13 24 11 7 0 0 11 7 9 14 11 24. Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography VIII Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem
Next, we shift each of these numbers by −k = −7 modulo 26 to obtain 4 23 15 4 17 8 4 13 2 4 8 18 0 6 17 4 0 19 19 4 0 2 7 4 17. Finally, we translate these numbers back to letters to obtain the plaintext. We obtain “EXPERIENCE IS A GREAT TEACHER.”
RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Crytanalysis Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem
The process of recovering plaintext from ciphertext without knowledge of both the encryption method and the key is known as crytanalysis or breaking codes. In general, cryptanalysis is a difficult process, especially when the encryption method is unknown.
RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Public key cryptography I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption
Classical shift cipher is an examples of private key cryptosystems. In a private key cryptosystem, once you know an encryption key, you can quickly find the decryption key. So, knowing how to encrypt messages using a particular key allows you to decrypt messages that were encrypted using this key. For example, when a shift cipher is used with encryption key k, the plaintext integer p is sent to c = (p + k) mod 26.
RSA Decryption Portfolio Problem
Decryption is carried out by shifting by −k; that is, p = (c − k) mod 26. Dr. Ramdas B. Sonawane
Applications of Mathematics
Public key cryptography II Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
So knowing how to encrypt with a shift cipher also tells you how to decrypt. When a private key cryptosystem is used, two parties who wish to communicate in secret must share a secret key. Because anyone who knows this key can both encrypt and decrypt messages, two people who want to communicate securely need to securely exchange this key. To avoid the need for keys to be shared by every pair of parties that wish to communicate securely, in the 1970s cryptologists introduced the concept of public key cryptosystems. In public key cryptography, knowing how to encrypt does not also tell someone how to decrypt. The most widely Dr. Ramdas B. Sonawane
Applications of Mathematics
Public key cryptography III Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography
used public key system, called the RSA cryptosystem, encrypts messages using modular exponentiation, where the modulus is the product of two large primes.
The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
The RSA Cryptosystem I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
In 1976, three researchers at the Massachusetts Institute of Technology - Ronald Rivest, Adi Shamir, and LeonardAdleman -introduced to the world a public key cryptosystem, known as the RSA system, from the initials of its inventors. In the RSA cryptosystem, each individual has an encryption key (n, e) where n = pq, the modulus is the product of two large primes p and q, say with 200 digits each, and an exponent e that is relatively prime to (p − 1)(q − 1). To produce a usable key, two large primes must be found. This can be done quickly on a computer using probabilistic primality tests. However, the product of these primes n = pq, with approximately 400 digits, cannot, as far as is currently known, be factored in a reasonable length of time. Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA encryption I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
To encrypt messages using a particular key (n, e), we first translate a plaintext message M into sequences of integers. To do this, we first translate each plaintext letter into a twodigit number, using the same translation we employed for shift ciphers, with one key difference. That is, we include an initial zero for the letters A through J, so that A is translated into 00, B into 01,... , and J into 09. Then, we concatenate these two-digit numbers into strings of digits. Next, we divide this string into equally sized blocks of 2N digits, where 2N is the largest even number such that the number 2525... 25 with 2N digits does not exceed n. Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA encryption II Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption
we translate the plaintext message M into a sequence of integers m1, m2, · · · , mk for some integer k. Encryption proceeds by transforming each block mi to a ciphertext block ci . This is done using the function C = Me
mod n.
We leave the encrypted message as blocks of numbers and send these to the intended recipient.
Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA encryption III Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography
Example 4. Encrypt the message STOP using the RSA cryptosystem with key (2537, 13). Note that 2537 = 43 × 59, p = 43 and q = 59 are primes, and
Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
gcd(e, (p − 1)(q − 1)) = gcd(13, 42 × 58) = 1. solution To encrypt, we first translate the letters in STOP into their numerical equivalents. We then group these numbers into blocks of four digits (because 2525 < 2537 < 252525), to obtain 1819 1415. Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA encryption IV Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption
We encrypt each block using the mapping C = M 13
mod 2537.
Computations using fast modular multiplication show that 181913 mod 2537 = 2081 and 141513 mod 2537 = 2182. The encrypted message is 2081 2182.
RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA Decryption I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem
The plaintext message can be quickly recovered from a ciphertext message when the decryption key d, an inverse of e modulo (p − 1)(q − 1), is known. [Such an inverse exists because gcd(e, (p − 1)(q − 1)) = 1.] To see this, note that if de = 1( mod (p − 1)(q − 1)), there is an integer k such that de = 1 + k(p − 1)(q − 1). It follows that C d = (M e )d = M de = M 1+k(p−1)(q−1) ( mod n).
RSA encryption RSA Decryption Portfolio Problem
By Fermat’s little theorem [assuming that gcd(M, p) = gcd(M, q) = 1, it follows that M p−1 = 1( mod p) and M q−1 = 1( mod q). Consequently, Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA Decryption II Applications of Mathematics Dr. Ramdas B. Sonawane
C d = M · (M p−1 ) k(q−1) = M · 1 = M( mod p) and
Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
C d = M · (M q−1 ) k(p−1) = M · 1 = M( mod q). Because gcd(p, q) = 1, it follows by the Chinese remainder theorem that C d = M( mod pq). Example 5. We receive the encrypted message 0981 0461. What is the decrypted message if it was encrypted using the RSA cipher from previous Example 4? Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA Decryption III Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
solution The message was encrypted using the RSA cryptosystem with n = 43 · 59 and exponent 13. d = 937 is an inverse of 13 modulo 42 · 58 = 2436. We use 937 as our decryption exponent. Consequently, to decrypt a block C, we compute M = C 937 mod 2537. To decrypt the message, we use the fast modular exponentiation algorithm to compute 0981937 mod 2537 = 0704 and 0461937 mod 2537 = 1115. Consequently, the numerical version of the original message is 0704 1115. Translating this back to English letters, we see that the message is HELP. Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Suppose a person has some wealth. He wants to invest it and earn. There are many ways, he do it. He can invest it in real estate, can purchase gold, can deposit in banks, invest in stock market etc. He can gain highest returns from stock market. There are many kinds of information that might be used to predict the performance of stocks: general economic conditions, health of industry which the stock represents, productivity of the company as reflected in its annual report, success of the company’s competitors, and so on. Here we will study the approach using stock quotations and some statistics to define and estimate average rate of return on investment and the risk of investment. We use the technique of Lagrange multipliers to put together an Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem II Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption
optimal portfolio to investment. The problem of choosing an optimal combination of investments is known as the “Portfolio Problem”. Suppose that we are following four possible investments, whose market prices per share today are P1, P2, P3 and P4 . Let the prices for the same stocks tomorrow be denoted by Q1, Q2, Q3 and Q4 . The rate of return on the investment, that is the gain in value per rupee paid on stock i, is
RSA Decryption Portfolio Problem
Ri =
Dr. Ramdas B. Sonawane
Qi − Pi . Pi
Applications of Mathematics
Portfolio Problem III Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
For example we have recorded the prices of the common stocks of four companies trading on the Bombay Stock Exchange. We followed the stocks over a period of seventeen trading days. The numbers in the rate of return columns are obtained by dividing the difference (current price minus previous price) by the previous price. Taking the arithmetical average of those observed rates of return gives the estimates of ρ1 , ρ2, ρ3 , and ρ4 listed in the row labeled ’Mean’.
Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem IV Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem V Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Table suggests that there is variability in the rates of return. Typically, risky investments which have high average rates of return also have high risks. If this is not the case, the investors will all flock to high-reward, low-risk investments, and market imbalances will occur. To increase safety, investors tend to diversify, that is, to spread their wealth among several opportunities, hence constructing a collection of portfolio of investments. Suppose the investor has total wealth W, then the decision to be made is what fraction wi of that wealth is to be devoted to investment i, for i = 1, 2, 3, 4. The total wealth invested in investment i is wi · W, and as the expected rate of return per rupee invested Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem VI Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption
is ρi , the expected return from our investment in investment i is ρi · wi · W. Summing over all four investments, the total return expected is ρ1 · w1 · W + ρ2 · w2 · W + ρ3 · w3 · W + ρ4 · w4 · W . Since we invested W rupees, the rate of return for the portfolio per rupee is
RSA Decryption Portfolio Problem
ρ=
ρ1 · w1 · W + ρ2 · w2 · W + ρ3 · w3 · W + ρ4 · w4 · W . W Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem VII Applications of Mathematics
That is, ρ = ρ1 · w1 + ρ2 · w2 + ρ3 · w3 + ρ4 · w4 .
Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem
The variance V ar(R) = σ 2 of an uncertain rate of return is the average squared difference between the rate of return R and its mean ρ. In the portfolio problem we will need to consider the risk or variance of the portfolio’s actual rate of return, which is
RSA encryption
Rp = R1 · w1 + R2 · w2 + R3 · w3 + R4 · w4 .
RSA Decryption Portfolio Problem
Thus, V ar(Rp ) = V ar(R1 · w1 + R2 · w2 + R3 · w3 + R4 · w4 ). Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem VIII Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
That is, V ar(Rp ) = σ12 · w12 + σ22 · w22 + σ32 · w32 + σ42 · w42 . We have to maximize, ρ − aσ 2 , where a is a risk aversion factor which measures the reluctance to take risk. For example a = 0 means that you don’t mind taking risk at all, your only goal is to maximize average rate of return. If a = 10, then an increase of one unit in risk will have to be offset by an increase in 10 units of return in order to value the investment in the same way. A larger value of a means more worry about risk. Now we are having the portfolio problem which is the constrained optimization problem. Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem IX Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography
Max. f (w1, w2, w3, w4 ) = ρ1 w1 + ρ2 w2 + ρ3 w3 + ρ4 w4 −a(σ12 w12 + σ22 w22 ) −a(σ32 w32 + σ42 w42 ) sub. to g(w1, w2, w3, w4 ) = w1 + w2 + w3 + w4 − 1 = 0.
Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Using Lagrange’s multiplier method we get a system of equations in the unknowns λ, w1 , w2 , w3 and w4 : ρ1 − 2aσ12 w1 ρ2 − 2aσ22 w2 ρ3 − 2aσ32 w3 ρ4 − 2aσ42 w4 w1 + w2 + w3 + w4 Dr. Ramdas B. Sonawane
= λ, = λ, = λ, = λ, = 1.
Applications of Mathematics
Portfolio Problem X Applications of Mathematics Dr. Ramdas B. Sonawane
From these equations we get values of w2 , w3 and w4 in of w1 as follows:
Cryptography
w2 =
Classical Cryptography
w3 =
Crytanalysis Classical Cryptography
w4 =
The RSA Cryptosystem RSA encryption
Thus
RSA Decryption Portfolio Problem
w1 =
Dr. Ramdas B. Sonawane
1−
(ρ2 −ρ1 )+2aσ12 w1 , 2aσ22 2 (ρ3 −ρ1 )+2aσ1 w1 , 2aσ32 2 (ρ4 −ρ1 )+2aσ1 w1 . 2aσ42
(ρ2 −ρ1 ) (ρ3 −ρ1 ) (ρ4 −ρ1 ) − − 2aσ 2 2aσ 2 2aσ 2 2 3 4 2 2 2 σ σ σ 1 1 1 1+ 2 + 2 + 2 σ σ σ 2 3 4
Applications of Mathematics
.
Portfolio Problem XI Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography
Similarly we get values of w2 , w3 and w4 . Numerical computations for several values of risk aversion a and mean and variances from table 1, results in the following solution:
Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography
Thank You
The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Applications of Mathematics
Crytanalysis Classical Cryptography The RSA Cryptosystem
Dr. Ramdas B. Sonawane Ness Wadia College of Commerce, Pune
RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Cryptography I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis
The subject of transforming information so that it cannot be easily recovered without special knowledge. Inventing cipher systems; protecting communications and storage.
Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Cryptography II Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
The earliest known of cryptography was by Julius Caesar. He made messages secret by shifting each letter three letters forward in the alphabet. For instance, using this scheme the letter B is sent to E and the letter X is sent to A. This is an example of encryption, that is, the process of making a message secret. Caesar’s encryption method can be represented by the function f that assigns to the nonnegative integer p, p ≤ 25, the integer f (p) in the set {0, 1, 2, · · · , 25} with f (p) = (p + 3) mod 26. Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography II Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography
In the encrypted version of the message, the letter represented by p is replaced with the letter represented by (p + 3) mod 26.
The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography III Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Example 1. What is the secret message produced from the message “MEET YOU IN THE PARK” using the Caesar cipher? solution First replace the letters in the message with numbers. This produces 12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10. Now replace each of these numbers p by f (p) = (p + 3) mod 26. This gives 15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13. Translating this back to letters produces the encrypted message “PHHW BRX LQ WKH SDUN.” Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography IV Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
To recover the original message from a secret message encrypted by the Caesar cipher, the function f −1 , the inverse of f , is used. Note that the function f −1 sends an integer p from Z26 , to f −1 (p) = (p − 3) mod 26. i.e. to find the original message, each letter is shifted back three letters in the alphabet, with the first three letters sent to the last three letters of the alphabet. The process of determining the original message from the encrypted message is called decryption. There are various ways to generalize the Caesar cipher. For example, instead of shifting the numerical equivalent of Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography V Applications of Mathematics Dr. Ramdas B. Sonawane
each letter by 3, we can shift the numerical equivalent of each letter by k, so that
Cryptography Classical Cryptography
f (p) = (p + k)
mod 26.
Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption
Such a cipher is called a shift cipher. Note that decryption can be carried out using f −1 (p) = (p − k) mod 26.
RSA Decryption Portfolio Problem
Here the integer k is called a key.
Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography VI Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Example 2. Encrypt the plaintext message “STOP GLOBAL WARMING” using the shift cipher with shift k = 11. solution To encrypt the message “STOP GLOBAL WARMING” we first translate each letter to the corresponding element of Z26 . This produces the string 18 19 14 15 6 11 14 1 0 11 22 0 17 12 8 13 6. We now apply the shift f (p) = (p + 11) mod 26 to each number in this string. We obtain 3 4 25 0 17 22 25 12 11 22 7 11 2 23 19 24 17. Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography VII Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Translating this last string back to letters, we obtain the ciphertext “DEZA RWZMLW HLCXTYR.” Example 3. Decrypt the ciphertext message “LEWLYPLUJL PZ H NYLHA ALHJOLY” that was encrypted with the shift cipher with shift k = 7. solution To decrypt the ciphertext “LEWLYPLUJL PZ H NYLHA ALHJOLY” we first translate the letters back to elements of Z26 . We obtain 11 4 22 11 24 15 11 20 9 11 15 25 7 13 24 11 7 0 0 11 7 9 14 11 24. Dr. Ramdas B. Sonawane
Applications of Mathematics
Classical Cryptography VIII Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem
Next, we shift each of these numbers by −k = −7 modulo 26 to obtain 4 23 15 4 17 8 4 13 2 4 8 18 0 6 17 4 0 19 19 4 0 2 7 4 17. Finally, we translate these numbers back to letters to obtain the plaintext. We obtain “EXPERIENCE IS A GREAT TEACHER.”
RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Crytanalysis Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem
The process of recovering plaintext from ciphertext without knowledge of both the encryption method and the key is known as crytanalysis or breaking codes. In general, cryptanalysis is a difficult process, especially when the encryption method is unknown.
RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Public key cryptography I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption
Classical shift cipher is an examples of private key cryptosystems. In a private key cryptosystem, once you know an encryption key, you can quickly find the decryption key. So, knowing how to encrypt messages using a particular key allows you to decrypt messages that were encrypted using this key. For example, when a shift cipher is used with encryption key k, the plaintext integer p is sent to c = (p + k) mod 26.
RSA Decryption Portfolio Problem
Decryption is carried out by shifting by −k; that is, p = (c − k) mod 26. Dr. Ramdas B. Sonawane
Applications of Mathematics
Public key cryptography II Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
So knowing how to encrypt with a shift cipher also tells you how to decrypt. When a private key cryptosystem is used, two parties who wish to communicate in secret must share a secret key. Because anyone who knows this key can both encrypt and decrypt messages, two people who want to communicate securely need to securely exchange this key. To avoid the need for keys to be shared by every pair of parties that wish to communicate securely, in the 1970s cryptologists introduced the concept of public key cryptosystems. In public key cryptography, knowing how to encrypt does not also tell someone how to decrypt. The most widely Dr. Ramdas B. Sonawane
Applications of Mathematics
Public key cryptography III Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography
used public key system, called the RSA cryptosystem, encrypts messages using modular exponentiation, where the modulus is the product of two large primes.
The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
The RSA Cryptosystem I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
In 1976, three researchers at the Massachusetts Institute of Technology - Ronald Rivest, Adi Shamir, and LeonardAdleman -introduced to the world a public key cryptosystem, known as the RSA system, from the initials of its inventors. In the RSA cryptosystem, each individual has an encryption key (n, e) where n = pq, the modulus is the product of two large primes p and q, say with 200 digits each, and an exponent e that is relatively prime to (p − 1)(q − 1). To produce a usable key, two large primes must be found. This can be done quickly on a computer using probabilistic primality tests. However, the product of these primes n = pq, with approximately 400 digits, cannot, as far as is currently known, be factored in a reasonable length of time. Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA encryption I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
To encrypt messages using a particular key (n, e), we first translate a plaintext message M into sequences of integers. To do this, we first translate each plaintext letter into a twodigit number, using the same translation we employed for shift ciphers, with one key difference. That is, we include an initial zero for the letters A through J, so that A is translated into 00, B into 01,... , and J into 09. Then, we concatenate these two-digit numbers into strings of digits. Next, we divide this string into equally sized blocks of 2N digits, where 2N is the largest even number such that the number 2525... 25 with 2N digits does not exceed n. Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA encryption II Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption
we translate the plaintext message M into a sequence of integers m1, m2, · · · , mk for some integer k. Encryption proceeds by transforming each block mi to a ciphertext block ci . This is done using the function C = Me
mod n.
We leave the encrypted message as blocks of numbers and send these to the intended recipient.
Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA encryption III Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography
Example 4. Encrypt the message STOP using the RSA cryptosystem with key (2537, 13). Note that 2537 = 43 × 59, p = 43 and q = 59 are primes, and
Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
gcd(e, (p − 1)(q − 1)) = gcd(13, 42 × 58) = 1. solution To encrypt, we first translate the letters in STOP into their numerical equivalents. We then group these numbers into blocks of four digits (because 2525 < 2537 < 252525), to obtain 1819 1415. Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA encryption IV Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption
We encrypt each block using the mapping C = M 13
mod 2537.
Computations using fast modular multiplication show that 181913 mod 2537 = 2081 and 141513 mod 2537 = 2182. The encrypted message is 2081 2182.
RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA Decryption I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem
The plaintext message can be quickly recovered from a ciphertext message when the decryption key d, an inverse of e modulo (p − 1)(q − 1), is known. [Such an inverse exists because gcd(e, (p − 1)(q − 1)) = 1.] To see this, note that if de = 1( mod (p − 1)(q − 1)), there is an integer k such that de = 1 + k(p − 1)(q − 1). It follows that C d = (M e )d = M de = M 1+k(p−1)(q−1) ( mod n).
RSA encryption RSA Decryption Portfolio Problem
By Fermat’s little theorem [assuming that gcd(M, p) = gcd(M, q) = 1, it follows that M p−1 = 1( mod p) and M q−1 = 1( mod q). Consequently, Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA Decryption II Applications of Mathematics Dr. Ramdas B. Sonawane
C d = M · (M p−1 ) k(q−1) = M · 1 = M( mod p) and
Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
C d = M · (M q−1 ) k(p−1) = M · 1 = M( mod q). Because gcd(p, q) = 1, it follows by the Chinese remainder theorem that C d = M( mod pq). Example 5. We receive the encrypted message 0981 0461. What is the decrypted message if it was encrypted using the RSA cipher from previous Example 4? Dr. Ramdas B. Sonawane
Applications of Mathematics
RSA Decryption III Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
solution The message was encrypted using the RSA cryptosystem with n = 43 · 59 and exponent 13. d = 937 is an inverse of 13 modulo 42 · 58 = 2436. We use 937 as our decryption exponent. Consequently, to decrypt a block C, we compute M = C 937 mod 2537. To decrypt the message, we use the fast modular exponentiation algorithm to compute 0981937 mod 2537 = 0704 and 0461937 mod 2537 = 1115. Consequently, the numerical version of the original message is 0704 1115. Translating this back to English letters, we see that the message is HELP. Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem I Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Suppose a person has some wealth. He wants to invest it and earn. There are many ways, he do it. He can invest it in real estate, can purchase gold, can deposit in banks, invest in stock market etc. He can gain highest returns from stock market. There are many kinds of information that might be used to predict the performance of stocks: general economic conditions, health of industry which the stock represents, productivity of the company as reflected in its annual report, success of the company’s competitors, and so on. Here we will study the approach using stock quotations and some statistics to define and estimate average rate of return on investment and the risk of investment. We use the technique of Lagrange multipliers to put together an Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem II Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption
optimal portfolio to investment. The problem of choosing an optimal combination of investments is known as the “Portfolio Problem”. Suppose that we are following four possible investments, whose market prices per share today are P1, P2, P3 and P4 . Let the prices for the same stocks tomorrow be denoted by Q1, Q2, Q3 and Q4 . The rate of return on the investment, that is the gain in value per rupee paid on stock i, is
RSA Decryption Portfolio Problem
Ri =
Dr. Ramdas B. Sonawane
Qi − Pi . Pi
Applications of Mathematics
Portfolio Problem III Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
For example we have recorded the prices of the common stocks of four companies trading on the Bombay Stock Exchange. We followed the stocks over a period of seventeen trading days. The numbers in the rate of return columns are obtained by dividing the difference (current price minus previous price) by the previous price. Taking the arithmetical average of those observed rates of return gives the estimates of ρ1 , ρ2, ρ3 , and ρ4 listed in the row labeled ’Mean’.
Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem IV Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem V Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Table suggests that there is variability in the rates of return. Typically, risky investments which have high average rates of return also have high risks. If this is not the case, the investors will all flock to high-reward, low-risk investments, and market imbalances will occur. To increase safety, investors tend to diversify, that is, to spread their wealth among several opportunities, hence constructing a collection of portfolio of investments. Suppose the investor has total wealth W, then the decision to be made is what fraction wi of that wealth is to be devoted to investment i, for i = 1, 2, 3, 4. The total wealth invested in investment i is wi · W, and as the expected rate of return per rupee invested Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem VI Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption
is ρi , the expected return from our investment in investment i is ρi · wi · W. Summing over all four investments, the total return expected is ρ1 · w1 · W + ρ2 · w2 · W + ρ3 · w3 · W + ρ4 · w4 · W . Since we invested W rupees, the rate of return for the portfolio per rupee is
RSA Decryption Portfolio Problem
ρ=
ρ1 · w1 · W + ρ2 · w2 · W + ρ3 · w3 · W + ρ4 · w4 · W . W Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem VII Applications of Mathematics
That is, ρ = ρ1 · w1 + ρ2 · w2 + ρ3 · w3 + ρ4 · w4 .
Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem
The variance V ar(R) = σ 2 of an uncertain rate of return is the average squared difference between the rate of return R and its mean ρ. In the portfolio problem we will need to consider the risk or variance of the portfolio’s actual rate of return, which is
RSA encryption
Rp = R1 · w1 + R2 · w2 + R3 · w3 + R4 · w4 .
RSA Decryption Portfolio Problem
Thus, V ar(Rp ) = V ar(R1 · w1 + R2 · w2 + R3 · w3 + R4 · w4 ). Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem VIII Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
That is, V ar(Rp ) = σ12 · w12 + σ22 · w22 + σ32 · w32 + σ42 · w42 . We have to maximize, ρ − aσ 2 , where a is a risk aversion factor which measures the reluctance to take risk. For example a = 0 means that you don’t mind taking risk at all, your only goal is to maximize average rate of return. If a = 10, then an increase of one unit in risk will have to be offset by an increase in 10 units of return in order to value the investment in the same way. A larger value of a means more worry about risk. Now we are having the portfolio problem which is the constrained optimization problem. Dr. Ramdas B. Sonawane
Applications of Mathematics
Portfolio Problem IX Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography
Max. f (w1, w2, w3, w4 ) = ρ1 w1 + ρ2 w2 + ρ3 w3 + ρ4 w4 −a(σ12 w12 + σ22 w22 ) −a(σ32 w32 + σ42 w42 ) sub. to g(w1, w2, w3, w4 ) = w1 + w2 + w3 + w4 − 1 = 0.
Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Using Lagrange’s multiplier method we get a system of equations in the unknowns λ, w1 , w2 , w3 and w4 : ρ1 − 2aσ12 w1 ρ2 − 2aσ22 w2 ρ3 − 2aσ32 w3 ρ4 − 2aσ42 w4 w1 + w2 + w3 + w4 Dr. Ramdas B. Sonawane
= λ, = λ, = λ, = λ, = 1.
Applications of Mathematics
Portfolio Problem X Applications of Mathematics Dr. Ramdas B. Sonawane
From these equations we get values of w2 , w3 and w4 in of w1 as follows:
Cryptography
w2 =
Classical Cryptography
w3 =
Crytanalysis Classical Cryptography
w4 =
The RSA Cryptosystem RSA encryption
Thus
RSA Decryption Portfolio Problem
w1 =
Dr. Ramdas B. Sonawane
1−
(ρ2 −ρ1 )+2aσ12 w1 , 2aσ22 2 (ρ3 −ρ1 )+2aσ1 w1 , 2aσ32 2 (ρ4 −ρ1 )+2aσ1 w1 . 2aσ42
(ρ2 −ρ1 ) (ρ3 −ρ1 ) (ρ4 −ρ1 ) − − 2aσ 2 2aσ 2 2aσ 2 2 3 4 2 2 2 σ σ σ 1 1 1 1+ 2 + 2 + 2 σ σ σ 2 3 4
Applications of Mathematics
.
Portfolio Problem XI Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography
Similarly we get values of w2 , w3 and w4 . Numerical computations for several values of risk aversion a and mean and variances from table 1, results in the following solution:
Classical Cryptography Crytanalysis Classical Cryptography The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Applications of Mathematics Dr. Ramdas B. Sonawane Cryptography Classical Cryptography Crytanalysis Classical Cryptography
Thank You
The RSA Cryptosystem RSA encryption RSA Decryption Portfolio Problem
Dr. Ramdas B. Sonawane
Applications of Mathematics
Related Documents 543cg
Applications Of Mathematics 6p1v4h
December 2019 62
Applications Of Mathematics In Our Daily Life 5u4i68
December 2019 45
November 2021 0
Pharmaceutical Mathematics With Applications To Pharmacy 4d1r2v
November 2019 42
Applications Of Smart Dust 3p3n66
November 2019 32
Applications Of Gears 6k3q1y
October 2019 32More Documents from "Ramdas Sonawane" 6uu3h
Applications Of Mathematics 6p1v4h
December 2019 62
Asus Eee Pc P900.pdf 5qp2g
May 2022 0
Lg Laptop Motherboard Schematic Diagram.pdf 3ii22
December 2019 161
Motherboard Repairing Method.pdf 5d351s
November 2021 0
Lenovo E43 73p59
December 2019 78