Codebusters C

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

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
State: -

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: 314
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.

Season's over, I can sleep now.
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: 314
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.

Season's over, I can sleep now.
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 0 guests