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

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

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

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

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

Season's over, I can sleep now.

2019 Nats
Code Busters(16), DD(40), FQ(39), Forensics(36), WQ(27)

2018 Nats
CriB(26), DP (11), FF(1), MM(14), P&P(6)

2017 Nats
CriB(36), DD(35), FF(2), MM(20)

UTF-8 U+6211 U+662F
Exalted Member
Exalted Member
Posts: 1465
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

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

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.

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

Season's over, I can sleep now.

2019 Nats
Code Busters(16), DD(40), FQ(39), Forensics(36), WQ(27)

2018 Nats
CriB(26), DP (11), FF(1), MM(14), P&P(6)

2017 Nats
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: 1465
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

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

Re: Codebusters C

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

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

rafaelnadal
Member
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

Postby rafaelnadal » March 12th, 2019, 8:39 pm

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 :,)

advice is appreiciated uwu

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/-
We've Got Your Number: -/2/-/1/1/-

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

Re: Codebusters C

Postby Vortexx » March 12th, 2019, 9:41 pm

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 :,)

advice is appreiciated uwu

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
Member
Posts: 8
Joined: March 11th, 2019, 8:27 pm

Re: Codebusters C

Postby Scrambledeggs » March 12th, 2019, 10:13 pm

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

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

Re: Codebusters C

Postby Name » March 12th, 2019, 10:30 pm

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.
South Woods MS (5 medals)/Syosset HS (24 medals)
Favorite Past Events: Microbe, Invasive, Matsci, Fermi
Next Year: Astro, Code, hopefully Orni, and maybe Compound
2018-19 highlights
mit- 1st code, 3rd fermi
cornell- 1st fermi
states- 1st fermi, 3rd astro, 3rd code
19 medals

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

Re: Codebusters C

Postby Araluen » March 13th, 2019, 8:39 pm

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.


Return to “Lab Events”

Who is online

Users browsing this forum: No registered users and 1 guest