Friday Presentations AEB 320, 8:00 am to 9:25 am. 1. Joseph Pugliano and Brandon Sehestedt Title: Cryptography: Matrices and Encryption 2. Matt Westberg and Alex Hawks Title: Cracking the Hill-Cipher: how to break an encrypted message 3. Adam Lee Title: Image Compression with Haar Wavelets 4. Mark Van der Merwe, Ann Wilcox, Andrew Haas Title: Comparison and Optimization of SVD and DCT Image Compression Algorithms 5. Jeremy Jakobs and Nathan Rogers Title: Applications in genetics 1. ================= Joseph Pugliano Brandon Sehestedt Title: Cryptography: Matrices and Encryption Abstract: A study of hill cyphers and how to generate keys to encode and decode messages. We will also show the effectiveness of hill cyphers and investigate other means to encrypt messages that might be more effective. Table of Contents: • Intro – One minute • What is a hill cypher and its history – Four minutes • How to generate a key and decode them together – Two minutes • Discussion on how effective the encoding is – Two minutes • Brief discussion on more effective encryption methods – One minute joejoepugliano@gmail.com sehestedt89@gmail.com 2. ================== Matt Westberg Alex Hawks Title: Cracking the Hill-Cipher: how to break an encrypted message Abstract: Password encryption is used today in storing passwords in databases, and even to pass messages. While encrypting messages can be useful when attempting to pass a message, this project focuses more on the cracking of these encrypted messages. When enough sample sizes are gathered from both the message, and the coded message, the key matrix can be solved. There are many ways to crack messages, but this project will focus primarily on cracking the Hill-Cipher. Background information: The Hill-Cipher is an encrypted method based on linear algebra that takes a message then converts it to numbers assigned to each letter in that message. This numerical message is then transformed into a matrix, which is then multiplied by a key matrix that is invertible. After doing so, this matrix undergoes modulo operation of the size of alphabet. For instance, if the alphabet is standard from A-Z, one would modulo 26 for the 26 letters. The decryption process is the opposite. One will find the inverse of the key matrix, continuing to apply the modulo value, to keep the numbers within the range of the alphabet. After doing so, one multiplies the inverse matrix with the coded numerical values. After applying the modulo operation, this will give the original message. Cracking the Hill-Cipher: Cracking the code means obtaining the key matrix so that if any other encrypted message is given one would be able to decode the message. When attempting to crack a code, it is important that enough information is gathered. If the key matrix is a N x N matrix, it will be necessary to obtain N^2 messages and encryptions. For example, if the key matrix is a 2x2 matrix, it will be necessary to obtain 2 messages and their corresponding 2 encryptions. Summary of results: The results that we found were that if given enough information, it was in fact possible to find the key matrix to the encryption. The trick is to have enough message to find linearly independent column vectors. If column vectors (encrypted numerical values) are linearly dependent, then those column vectors cannot be used in the process, and more data will be needed. We found that for a 2x2 key matrix, 2 encrypted messages and their 2 plaintext messages were sufficient to find the key matrix. To make the process more complex, we found that if someone were to use a 3x3 key matrix or a 4x4 key matrix, more intercepted messages and their meanings would be necessary to find the key matrix. Based on the results that we found, one strategy to increase the security of the encrypted code would be to use a larger key matrix. Mathematically speaking, as the key matrix increases in size, the number of intercepted messages and their meanings that are needed to crack the code would rise in a quadratic manner. matthew.westberg15@gmail.com 3. ================ Adam Lee Title: Image Compression with Haar Wavelets Abstract The Haar wavelet transform was created in 1910 by Alfred Haar. This project uses the Haar transform to construct an orthonormal basis, and then apply it to image compression. The compression process, transforms an image with the orthonormal basis, reduces it with a threshold value, epsilon, and then reverses the transform. This procedure compresses an image by slowly averaging adjacent pixels together. An example is shown with a grayscale image with the process extended to color images with the included MATLAB script. Adam.Lee@utah.edu 4. ================ Mark Van der Merwe Andrew Haas Ann Wilcox Title: Comparison and Optimization of SVD and DCT Image Compression Algorithms Abstract: For our project we will be comparing the efficiency of SVD and DCT. We will be comparing the how significant the visual deformation is to the decrease in file size for each compression algorithm. A bitmap image is compressed using singular value decomposition (SVD). Using Principal Component Analysis (PCA), we can throw out certain terms within a storage matrix, which will lower image quality but allow it to be stored for a fraction of the file size. Using compression algorithm Discrete Cosine Transform (DCT), we can separate an image into its frequencies and only keep "important" frequencies, again allowing us to shave off file size by sacrificing image quality. After comparing the two algorithms we will find the point where the file size is decreased as much as possible without a significant difference in image quality. Table of Contents: 1. Singular Value Decomposition Compression Algorithm a. Procedure of SVD Compression i. Decompose into Matrices ii. Remove values iii. Recompose Matrix b. Testing on Images i. Compression ratio c. Data Analysis i. Optimization of Algorithm 1. Image quality vs. Compression ratio. 2. Discrete Cosine Transform Compression Algorithm a. Procedure of DCT Compression i. Separate image into frequencies ii. Remove “unimportant” frequencies b. Testing on Images i. Compression ratio c. Data Analysis i. Optimization of Algorithm 1. Image quality vs. Compression ratio. 3. Comparison of SVD and DCT a. Comparison of algorithm “efficiency” u0920663@utah.edu == Mark Van der Merwe andhaas1@gmail.com == Andrew Haas u0783377@utah.edu == Ann Wilcox 5. ================== Jeremy Jakobs Nathan Rogers Title: Applications in genetics Abstract: Using linear algebraic techniques to model heredity. Particularly, how the genes AA, Aa, and aa are passed down from generation to generation. The process of heredity is pretty simple, but it can be useful to know how heredity is affected over longer periods of time and these calculations can be simplified using linear algebra. Some of the techniques we will use in particular include: Diagonalization, Eigenvalues/vectors, and the inverse of a matrix. Table of contents: - Introduction - graphs/ visualization of the problem at hand - solving the problem - conclusion and explanation of techniques used. u0497179@utah.edu shutout13@gmail.com