Codebusters C

C8H10N4O2!
Member
Member
Posts: 44
Joined: October 4th, 2018, 3:55 pm

Re: Codebusters C

Postby C8H10N4O2! » February 28th, 2019, 4:02 pm

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

Re: Codebusters C

Postby CongminhTran » March 2nd, 2019, 5:59 pm

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: 4
Joined: March 2nd, 2019, 3:42 pm
Division: C
State: CA

Re: Codebusters C

Postby modularmercury » March 2nd, 2019, 9:34 pm

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: 1518
Joined: January 18th, 2015, 7:42 am
Division: C
State: PA

Re: Codebusters C

Postby UTF-8 U+6211 U+662F » March 3rd, 2019, 11:27 am

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: 319
Joined: January 8th, 2018, 11:25 pm
Division: C
State: HI
Location: On Earth, I think

Re: Codebusters C

Postby jimmy-bond » March 3rd, 2019, 9:02 pm

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.
If life gives you melons, you're dyslexic.

Why can't dinosaurs ski? Because they're dead.

It's NNN, time to study.
Code Busters(16), DD(40), FQ(39), Forensics(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: 1518
Joined: January 18th, 2015, 7:42 am
Division: C
State: PA

Re: Codebusters C

Postby UTF-8 U+6211 U+662F » March 4th, 2019, 12:34 pm

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: 319
Joined: January 8th, 2018, 11:25 pm
Division: C
State: HI
Location: On Earth, I think

Re: Codebusters C

Postby jimmy-bond » March 4th, 2019, 8:06 pm

[Yes, the fraction should be mod 26, but the formula should still apply ?
The ad-bc and d, -b, -c, a still applies, yes
If life gives you melons, you're dyslexic.

Why can't dinosaurs ski? Because they're dead.

It's NNN, time to study.
Code Busters(16), DD(40), FQ(39), Forensics(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

Re: Codebusters C

Postby mcmn1619 » March 10th, 2019, 9:22 am

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: 1518
Joined: January 18th, 2015, 7:42 am
Division: C
State: PA

Re: Codebusters C

Postby UTF-8 U+6211 U+662F » March 10th, 2019, 2:38 pm

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

Re: Codebusters C

Postby mcmn1619 » March 11th, 2019, 9:12 pm

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


Return to “2019 Lab Events”

Who is online

Users browsing this forum: No registered users and 3 guests