## Codebusters C

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

### Re: Codebusters C

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
Posts: 2
Joined: October 12th, 2017, 4:17 pm
State: -

### Re: Codebusters C

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

### Re: Codebusters C

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

### Re: Codebusters C

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

jimmy-bond
Member
Posts: 283
Joined: January 8th, 2018, 11:25 pm
Division: C
State: HI
Location: On Earth, I think

### Re: Codebusters C

UTF-8 U+6211 U+662F wrote:You might as well just memorize a formula for the inverse matrix

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.

Roses are red, violets are blue, I have Alzheimer's, cheese on toast.

2019 Events

2018 Nats

2017 Nats

UTF-8 U+6211 U+662F
Exalted Member
Posts: 1368
Joined: January 18th, 2015, 7:42 am
Division: C
State: PA

### Re: Codebusters C

jimmy-bond wrote:
UTF-8 U+6211 U+662F wrote:You might as well just memorize a formula for the inverse matrix

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 ?

jimmy-bond
Member
Posts: 283
Joined: January 8th, 2018, 11:25 pm
Division: C
State: HI
Location: On Earth, I think

### Re: Codebusters C

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

Roses are red, violets are blue, I have Alzheimer's, cheese on toast.

2019 Events

2018 Nats

2017 Nats

mcmn1619
Member
Posts: 6
Joined: February 25th, 2018, 9:07 pm
Division: C
State: GA

### Re: Codebusters C

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

### Re: Codebusters C

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

$22a+22b \equiv 22\ (\textrm{mod } 26)$ and $22c+22d \equiv 4\ (\textrm{mod } 26)$ assuming the key is $\begin{pmatrix}a & b \\ c & d\end{pmatrix}$

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
Posts: 6
Joined: February 25th, 2018, 9:07 pm
Division: C
State: GA

### Re: Codebusters C

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

$22a+22b \equiv 22\ (\textrm{mod } 26)$ and $22c+22d \equiv 4\ (\textrm{mod } 26)$ assuming the key is $\begin{pmatrix}a & b \\ c & d\end{pmatrix}$

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

Member
Posts: 67
Joined: November 5th, 2016, 9:55 am
Division: C
State: TX
Location: Studying to win this bet i made *facepalm*

### Re: Codebusters C

It takes me 3 hours to finish a 19 question test how do i get faster :,,,,,,,)

also my partners never do anything on the actually test but they seem to get things in practice idk how to help them

i usually end up doing like 5-6 questions and my partners do like one question :,)

we usually split up they do aristocrat/paristrocrat, i do the rest :,) i finish and then try to help them but theres not much time

im better at math so i took affine/hill but should i try splitting it up differently >.< we rly need to get better but idk how to help my partners, and i myself can do all the codes but need to get much faster
CyFalls HS '19

2017 State: 2nd place We've Got Your Number

2018: 7L/Clements/Rice/Districts/Reg/States

Anatomy & Physiology:: 10/-/15/2/1/-
Experimental Design: 6/2/10/-/-
Microbe Mission: 12/5/8/4/2/-
Mousetrap Vehicle 17/6/9/5/2/-

Vortexx
Member
Posts: 30
Joined: November 19th, 2018, 8:35 am
State: IN

### Re: Codebusters C

rafaelnadal wrote:It takes me 3 hours to finish a 19 question test how do i get faster :,,,,,,,)

also my partners never do anything on the actually test but they seem to get things in practice idk how to help them

i usually end up doing like 5-6 questions and my partners do like one question :,)

we usually split up they do aristocrat/paristrocrat, i do the rest :,) i finish and then try to help them but theres not much time

im better at math so i took affine/hill but should i try splitting it up differently >.< we rly need to get better but idk how to help my partners, and i myself can do all the codes but need to get much faster

I don't know the strengths that you and your partners have but I can give some suggestions. It seems like your partners aren't that good at aristocrats and patristocrats, so I would suggest giving them ALL of the simple codes (Caesar, atbash, vigenere, baconian, affine) so you have more time to work on aristocrats and patristocrats. You can also have your partners do a lot more practice aristocrats and study letter frequencies and such so they can be more useful for the test. You shouldn't worry how fast you can do a test by yourself but instead try to improve your time on the codes that you excel at. People will be better at some codes than they are at others, and you need find out what these codes are for you and your partners. As for actually getting faster, make sure you are solving the code in the fastest possible way. Other than that, just practice. A lot. Good Luck!
[hide]Events|2017-Mission, Hovercraft
2018- Mission, Hover, Codebusters, Source Code

Scrambledeggs
Member
Posts: 6
Joined: March 11th, 2019, 8:27 pm

### Re: Codebusters C

Does anybody have good suggestions on patristocrats and baconain with 4 or more different symbols?

Name
Member
Posts: 248
Joined: January 21st, 2018, 4:41 pm
Division: C
State: NY
Location: Syosset

### Re: Codebusters C

Scrambledeggs wrote:Does anybody have good suggestions on patristocrats and baconain with 4 or more different symbols?

You can look for a pattern in determining A/B. For example vowels might be A and constanents might be B. Or i've seen it where A is A B is B C is a D is B etc. A is also more common then B (around twice as common). Also they could give you a couple of plaintext where you can get some of the A and Bs and fill in the rest of the cipher, kinda like a elaborate monoalphabetic.
SW 16-17 Syosset 18-21. Previous main events: Microbe, Invasive, Herp, Matsci
2018-19 Placements

Araluen
Member
Posts: 9
Joined: September 4th, 2018, 7:52 am
State: -

### Re: Codebusters C

Could someone answer my question about RSA? How exactly does encryption work? I know how to decode based on the toebes site, however all the examples on the site use numerical values for the ciphertext. Is it possible to send a message as the plaintext or does it have to be numbers? For example, how would i go about sending the word "codes"? Would I simply convert it to the numerical string "2143418" and encode that or do i have to mod it by the provided n value prior to encoding? Sorry for the string of questions.