Codebusters C

C8H10N4O2!
Member
Member
Posts: 44
Joined: October 4th, 2018, 3:55 pm
Has thanked: 0
Been thanked: 0

Re: Codebusters C

Post by C8H10N4O2! »

Can anyone please PM me an explanation for the Cornell RSA? I do not understand how do encode the string with numbers, and all of my attempts are nowhere near the answer key.
CongminhTran
Member
Member
Posts: 2
Joined: October 12th, 2017, 4:17 pm
Has thanked: 0
Been thanked: 0

Re: Codebusters C

Post by CongminhTran »

Hey guys,

I was just wondering if any of you guys could help me with the Hill Cipher, both decryption and encryption?

For encryption, how do you make an encryption matrix given plaintext- ciphertext letter pairs?

For decryption, how do you make a decryption matrix given plaintext-ciphertext letter pairs? Also, how do you decrypt when given a key and some ciphertext? Lastly, what if they ask you to produce a decryption matrix given only some plaintext (with number values all arranged in a matrix)? I was asking because at the Regionals test for my school, a couple of Hill Cipher questions where you had to produce A (the other one was THE) decryption matrix showed up, and we had no idea on how to do them.

If you guys could try to help, I would very much appreciate that!
modularmercury
Member
Member
Posts: 5
Joined: March 2nd, 2019, 3:42 pm
Division: C
State: CA
Has thanked: 0
Been thanked: 0

Re: Codebusters C

Post by modularmercury »

CongminhTran wrote:Hey guys,

I was just wondering if any of you guys could help me with the Hill Cipher, both decryption and encryption?

For encryption, how do you make an encryption matrix given plaintext- ciphertext letter pairs?

For decryption, how do you make a decryption matrix given plaintext-ciphertext letter pairs? Also, how do you decrypt when given a key and some ciphertext? Lastly, what if they ask you to produce a decryption matrix given only some plaintext (with number values all arranged in a matrix)? I was asking because at the Regionals test for my school, a couple of Hill Cipher questions where you had to produce A (the other one was THE) decryption matrix showed up, and we had no idea on how to do them.

If you guys could try to help, I would very much appreciate that!
Getting the encryption matrix given letters is pretty easy:

MATH

M A
T H

12 0
19 7

The method for decryption matrix is a little more complicated:

HILL

H I
L L

7 8
11 11

first find the determinant (ad - bc = 7 * 11 - 8 * 11 = -11 = 15 mod 26) and take its multiplicative inverse mod 26 (which would be 7 in this case)
then find the adjugate matrix which is the follwing for a 2 x 2 matrix:

a b
c d

is

d -b
-c a

which would be
11 -8
-11 7

multiply the adjugate matrix by the determinant's inverse and take the values mod 26 to get:

77 -56
-77 49

25 22
1 23

Z W
B X
simple matrix multiplication should confirm, hope this helped and sorry for the formatting
UTF-8 U+6211 U+662F
Exalted Member
Exalted Member
Posts: 1597
Joined: January 18th, 2015, 7:42 am
Division: C
State: PA
Has thanked: 6 times
Been thanked: 15 times

Re: Codebusters C

Post by UTF-8 U+6211 U+662F »

modularmercury wrote:
CongminhTran wrote:Hey guys,

I was just wondering if any of you guys could help me with the Hill Cipher, both decryption and encryption?

For encryption, how do you make an encryption matrix given plaintext- ciphertext letter pairs?

For decryption, how do you make a decryption matrix given plaintext-ciphertext letter pairs? Also, how do you decrypt when given a key and some ciphertext? Lastly, what if they ask you to produce a decryption matrix given only some plaintext (with number values all arranged in a matrix)? I was asking because at the Regionals test for my school, a couple of Hill Cipher questions where you had to produce A (the other one was THE) decryption matrix showed up, and we had no idea on how to do them.

If you guys could try to help, I would very much appreciate that!
Getting the encryption matrix given letters is pretty easy:

MATH

M A
T H

12 0
19 7

The method for decryption matrix is a little more complicated:

HILL

H I
L L

7 8
11 11

first find the determinant (ad - bc = 7 * 11 - 8 * 11 = -11 = 15 mod 26) and take its multiplicative inverse mod 26 (which would be 7 in this case)
then find the adjugate matrix which is the follwing for a 2 x 2 matrix:

a b
c d

is

d -b
-c a

which would be
11 -8
-11 7

multiply the adjugate matrix by the determinant's inverse and take the values mod 26 to get:

77 -56
-77 49

25 22
1 23

Z W
B X
simple matrix multiplication should confirm, hope this helped and sorry for the formatting
You might as well just memorize a formula for the inverse matrix
User avatar
jimmy-bond
Member
Member
Posts: 418
Joined: January 8th, 2018, 11:25 pm
Division: Grad
State: OH
Pronouns: He/Him/His
Has thanked: 11 times
Been thanked: 10 times

Re: Codebusters C

Post by jimmy-bond »

UTF-8 U+6211 U+662F wrote:You might as well just memorize a formula for the inverse matrix
Image
One of the tables provided in most tests is the modulo inverso table which goes something like:
1 3 5 7 9 11 15 17 19 21 23 25
1 9 21 15 3 19 7 23 11 5 17 25
(they're supposed to line up)
Instead of using the fractions, we take whatever is opposite on the table of the expression (ad-bc) mod 26.
PCHS, HI '21 | CWRU, OH '25
Code(16), DD(40), FQ(39),4&6(36), WQ(27)
CriB(26), DP (11), FF(1), MM(14), P&P(6)
CriB(36), DD(35), FF(2), MM(20)
UTF-8 U+6211 U+662F
Exalted Member
Exalted Member
Posts: 1597
Joined: January 18th, 2015, 7:42 am
Division: C
State: PA
Has thanked: 6 times
Been thanked: 15 times

Re: Codebusters C

Post by UTF-8 U+6211 U+662F »

jimmy-bond wrote:
UTF-8 U+6211 U+662F wrote:You might as well just memorize a formula for the inverse matrix
Image
One of the tables provided in most tests is the modulo inverso table which goes something like:
1 3 5 7 9 11 15 17 19 21 23 25
1 9 21 15 3 19 7 23 11 5 17 25
(they're supposed to line up)
Instead of using the fractions, we take whatever is opposite on the table of the expression (ad-bc) mod 26.
Yes, the fraction should be mod 26, but the formula should still apply ?
User avatar
jimmy-bond
Member
Member
Posts: 418
Joined: January 8th, 2018, 11:25 pm
Division: Grad
State: OH
Pronouns: He/Him/His
Has thanked: 11 times
Been thanked: 10 times

Re: Codebusters C

Post by jimmy-bond »

UTF-8 U+6211 U+662F wrote:[Yes, the fraction should be mod 26, but the formula should still apply ?
The ad-bc and d, -b, -c, a still applies, yes
PCHS, HI '21 | CWRU, OH '25
Code(16), DD(40), FQ(39),4&6(36), WQ(27)
CriB(26), DP (11), FF(1), MM(14), P&P(6)
CriB(36), DD(35), FF(2), MM(20)
mcmn1619
Member
Member
Posts: 6
Joined: February 25th, 2018, 9:07 pm
Division: C
State: GA
Has thanked: 0
Been thanked: 0

Re: Codebusters C

Post by mcmn1619 »

At regionals, I found a pretty challenging problem that I had no clue how to solve. (weighted the most on the test)

It was a Hill cipher, but instead of giving the encryption matrix or decryption matrix, they gave us 8 letters of plaintext and 8 letters of ciphertext and asked us to solve for the 2x2 encryption matrix.

I only remember the first pair, but the format was something like:

plaintext: WW aw ie ow

encryption: WE wo wi fs

I remember the first pair as WW --> WE because I spent an enormous amount of time looking for patterns in that ([-4,-4] --> [-4, 4] mod 26). All the letters had even indices except for like one or two of them. I feel like I'm just not familiar enough with modular arithmetic to solve the problem. After 40 minutes of cracking (our team managed to get most of the ciphers, and I still solved 2 others), I only knew which letters were even or odd. Any ideas on how to approach something like this?
UTF-8 U+6211 U+662F
Exalted Member
Exalted Member
Posts: 1597
Joined: January 18th, 2015, 7:42 am
Division: C
State: PA
Has thanked: 6 times
Been thanked: 15 times

Re: Codebusters C

Post by UTF-8 U+6211 U+662F »

mcmn1619 wrote:At regionals, I found a pretty challenging problem that I had no clue how to solve. (weighted the most on the test)

It was a Hill cipher, but instead of giving the encryption matrix or decryption matrix, they gave us 8 letters of plaintext and 8 letters of ciphertext and asked us to solve for the 2x2 encryption matrix.

I only remember the first pair, but the format was something like:

plaintext: WW aw ie ow

encryption: WE wo wi fs

I remember the first pair as WW --> WE because I spent an enormous amount of time looking for patterns in that ([-4,-4] --> [-4, 4] mod 26). All the letters had even indices except for like one or two of them. I feel like I'm just not familiar enough with modular arithmetic to solve the problem. After 40 minutes of cracking (our team managed to get most of the ciphers, and I still solved 2 others), I only knew which letters were even or odd. Any ideas on how to approach something like this?
Warning: I don't do this event, so my knowledge of it is a little shaky.

Convert both plaintext and encryption to a series of matrices. You should have four plaintext matrices and four encryption matrices. The goal is to find a matrix where key * plaintext = encryption. You can do this somewhat algebraically. If you use WW and WE, you get

and assuming the key is

Plug in the other pairs for more equations.

I don't know if there's an easier way, but there might be.

Note: 22 and -4 are equivalent mod 26, but I just find 22 easier to write.

Edit: aghhh forgot that A=0 and not A=1, changed some numbers
mcmn1619
Member
Member
Posts: 6
Joined: February 25th, 2018, 9:07 pm
Division: C
State: GA
Has thanked: 0
Been thanked: 0

Re: Codebusters C

Post by mcmn1619 »

UTF-8 U+6211 U+662F wrote:
mcmn1619 wrote:At regionals, I found a pretty challenging problem that I had no clue how to solve. (weighted the most on the test)

It was a Hill cipher, but instead of giving the encryption matrix or decryption matrix, they gave us 8 letters of plaintext and 8 letters of ciphertext and asked us to solve for the 2x2 encryption matrix.

I only remember the first pair, but the format was something like:

plaintext: WW aw ie ow

encryption: WE wo wi fs

I remember the first pair as WW --> WE because I spent an enormous amount of time looking for patterns in that ([-4,-4] --> [-4, 4] mod 26). All the letters had even indices except for like one or two of them. I feel like I'm just not familiar enough with modular arithmetic to solve the problem. After 40 minutes of cracking (our team managed to get most of the ciphers, and I still solved 2 others), I only knew which letters were even or odd. Any ideas on how to approach something like this?
Warning: I don't do this event, so my knowledge of it is a little shaky.

Convert both plaintext and encryption to a series of matrices. You should have four plaintext matrices and four encryption matrices. The goal is to find a matrix where key * plaintext = encryption. You can do this somewhat algebraically. If you use WW and WE, you get

and assuming the key is

Plug in the other pairs for more equations.

I don't know if there's an easier way, but there might be.

Note: 22 and -4 are equivalent mod 26, but I just find 22 easier to write.

Edit: aghhh forgot that A=0 and not A=1, changed some numbers
I do understand how to get the equations, but I just have no clue how to find the actual solution. Do I just have to do some bashing? I tried a good amount during the competition, but I think my logic was off because none of my solutions worked when I plugged them back into the equations.
Fermi / Chem Lab / Astro / Code Busters / Geo Map
Post Reply

Return to “2019 Lab Events”

Who is online

Users browsing this forum: No registered users and 0 guests