Computing with Pari presentation
ppt
CS556 Pari-GP Programming assignment 2
Suppose that both your plaintexts and ciphertexts are 98-letter blocks written in the usual 26-letter alphabet (consisting of A-Z), where the numerical equivalent of such a block is a 98-digit base-26 integer (written in order of decreasing powers of 26). Implement the El Gamal algorithm as follows:
- Initialization:
Generate a prime 512 bit prime p such that p-1=2.q, where q is a prime.
Take g=2 to be the generator of the group {{F}_{p}}^{*}. As g and p are public knowledge in the El Gamal system let g and p be global variables in your code.
Pick a secret key 'a' in the range 0 < a < p-1.
Write an encryption function which takes as input the following 98 entry array, encodes it into its numerical equivalent P, selects a random integer k and returns array [g^{k}, Pg^{ak}].
["I", "N", "T", "R", "O", "T", "O", "C", "R", "Y", "P", "T", "O", "O", "F", "F", "E", "R", "E", "D", "B", "Y", "T", "H", "E", "C", "O", "M", "P", "U", "T", "E", "R", "S", "C", "I", "E", "N", "C", "E", "D", "E", "P", "A", "R", "T", "M", "E", "N", "T", "A", "T", "T", "H", "E", "U", "N", "I", "V", "E", "R", "S", "I", "T", "Y", "O", "F", "S", "O", "U", "T", "H", "E", "R", "N", "C", "A", "L", "I", "F", "O", "R", "N", "I", "A", "L", "O", "S", "A", "N", "G", "E", "L", "E", "S", "U", "S", "A"]
- Write a decryption function takes an array of length 2 as input extracts P and computes it's alphabetic equivalent.
- Write the following to a file whose name is given as an input parameter to your main function.
- prime p,
- secret key a,
- random k,
- numerical equivalent of plaintext P,
- array returned by encryption function,
- alphabetic equivalent returned by decryption function.
Remarks.
- Refer to lecture notes 21-22 or Koblitz chapter IV section 3 for the El Gamal protocol.
- Refer to lecture notes 19-20 or Koblitz chapter V section 1 for details regarding the Solovay-Strassen test for compositeness.
- Take an integer to be a prime if it passes the Solovay-Strassen Test for 10 random choices of bases (this guarantees that the integer is a prime with probability atleast 1-(1/2)^10).
- Pari implements the Jacobi symbol as the kronecker function.
- Note the denominator in the Jacobi symbol needs to be a odd integer.
- Optimize your code using the squaring trick for exponentiation, etc.
Please mail your GP script file to me at burhanud@usc.edu by 12/06/02 (Friday). Don't forget to document your code and also write down your name and ID as comments at the start of your script.
CS556 Pari-GP Programming assignment 1
Suppose that both plaintexts and ciphertexts consist of trigraph message units, but while plaintexts are written in the 27-letter alphabet (consisting of A-Z and blank=26), ciphertexts are written in the 28-letter alphabet obtained by adding the symbol "/" (with numerical equivalent 27) to the 27-letter alphabet. We require that each user A choose n between 27^3=19683 and 28^3=21952, so that a plaintext trigraph in the 27-letter alphabet corresponds to a residue P modulo n, and then C=P^{e} mod n corresponds to a ciphertext trigraph in the 28-letter alphabet.
If your deciphering key is K=(n,d)=(21583,20787), decipher "YSNAUOZHXXH " (one blank at the end) with the help of a GP script (decryptf.gp) with a function (decryptf) which should take n,d and ciphertext string as input and return the plaintext string.
Step 1: Convert each ciphertext unit into it's numerical equivalent M.
Step 2: Use decryption function which takes n,d and M as input and returns P.
Step 3: Convert P to it's alphabetical equivalent
Step 4: Repeat
Please mail your GP script file to me at burhanud@usc.edu by 10/18/02 (Friday). Your scripts will be tested against the above n,d, ciphertext and also others. Don't forget to document your code and also write down your name and ID as comments at the start of your script.
String manipulation tip:
? Vec("pari")
%1 = ["p", "a", "r", "i"]
? concat(%)
%2 = "pari"
Unfortunately this tip doesn't seem to work on all versions on Pari. So input your ciphertext as a vector. ["p", "a", "r", "i"]
Trivia from the GP man page
Despite the leading G, GP has nothing to do with GNU. The first version was originally called GPC, for Great Programmable Calculator. For some reason, the trailing C was eventually dropped.
PARI has nothing to do with the French capital. The name is a pun about the project's early stages when the authors started to implement a library for "Pascal ARIthmetic" in the PASCAL programming language (they quickly switched to C).
For the benefit of non-native French speakers, here's a slightly expanded explanation: Blaise Pascal (1623-1662) was a famous French mathematician and philosopher who was one of the founders of probability and devised one of the first "arithmetic machines". He once proposed the following "proof" of the existence of God for the unbelievers: whether He exists or not I lose nothing by believing in Him, whereas if He does and I misbehave... This is the so-called "pari de Pascal" (Pascal's bet).
Note that PARI also means "fairy" in Persian.
``It was so fast, we thought it must have been written in French''
--Wieb Bosma, Luminy, 30
October 1997.