Thursday, June 20, 2024

Ed Scheidts Mayan Symbols

 ▉ In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue.

Mayan Symbols

I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols:

Figure 1 - Garage driveway of Ed Scheidt

We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can use Maps (iOS) to see their positions (See Figure 2):

Birds view of the driveway with marked positions of the two symbols
Figure 2 - Birds view of the driveway with marked positions of the two symbols

Monday, June 3, 2024

Proof: Otherwise you could break X

⬛ Some of you may be familiar with this situation. From time to time you find yourself thinking about a new approach to a problem that you know is difficult. And although you know that you should probably be doing something more productive, you try new ideas to tackle the problems.

And every now and then you stumble across a more or less basic fact that prevents your idea from working. I will try to give some examples that may surprise you. I will focus on the three main problems: discrete logarithm problem, factorization problem and the class number computation problem.

Often the examples come from situations that similar to:

    Alice: "I have a great idea. What if you could find some object O that has property P and Q."

    Bob: "Perfect, O is well known and P and Q seem not that restrictive."

A few days later.

    Alice: "I can not find such an object. All objects either have P or Q but not both."

    Bob: "Yeah, you are right, probably there is some theorem that we don't know."

There are probably many more examples or better ones. But at least all of the three examples below crossed my road during the last years.

Wednesday, October 12, 2022

Kryptos - The Cipher (Part 5)

ONE of the most surprising facts about Kryptos is that no one has yet discovered the expected way to find the keywords for K1 and K2. And perhaps this missing fact is the key to why we are stuck with K4. I don't think Sanborn wanted us to bruteforce the solutions (as we did), but somehow left a clue that we haven't seen yet.

Most people believe, that the morse code messages around Kryptos should somehow encode at least the first codeword for K1 (= Palimpsest). That's why the Morse code message are often called K0.

The Morse code messages are part of two pieces of granite with contained copper plates. I found two very interesting drawings of these two installations by Monet Friedrich on [1]:



Monday, November 2, 2020

RSA as Hidden Subgroup Problem

▍The Hidden Subgroup Problem is an important problem from Computer Science / Mathematics and actually covers several well known problems as a special case. The formal statement of the problem is:
Definition [Hidden Subgroup Problem (HSP)] Let $\mathbb{G}$ be a group and $\mathbb{H}$ an unknown subgroup of $\mathbb{G}$, i.e., $\mathbb{H} \leq \mathbb{G}$. Let $S$ be any set and $f$ be a function that maps the group elements of $\mathbb{G}$ to $S$, i.e., $f: \mathbb{G} \rightarrow S$. The function $S$ has the special property that it can distinguish cosets of $\mathbb{H}$: $$ f(e_1) = f(e_2) \Leftrightarrow e_1\mathbb{H} = e_2\mathbb{H} $$ The Problem is, given $\mathbb{G}$ and access to the function $f$, to determine a generating set for the subgroup $\mathbb{H}$ ∎ 
The notation $e\mathbb{H}$ denotes the coset $$e\mathbb{H} = \left\{eh | h \in \mathbb{H}\right\}$$. Problems that can be described as an instance of the HSP are for example:
  1. Integer Factorization Problem
  2. Discrete Logarithm Problem
  3. Shortest Vector Problem
  4. Deutsch Problem
  5. Simon's Problem
and probably many more. The definition of the HSP above seems very abstract, but the subgroup $\mathbb{H}$ actually covers the usual integers of interest, e.g. divisors of $\varphi(N)$ in case of the Factorization Problem or multiples of the exponents in question in case of the Discrete Logarithm Problem. Shors Algorithm is a special instance of an HSP-Solver that finds the period of the function $g^x \pmod{N}$, i.e., it finds divisors of $\varphi(N)$. However, his algorithm only works in the ablian case. How to solve the HSP efficiently for non abelian groups is not known, also for quantum computers. The Shortest Vector Problem is a hard problem for quantum computers. So it is no surprise, that the reduction from SVP to HSP brings into play a non abelian group, the dihidral group.

Tuesday, July 28, 2020

Kryptos - The Cipher (Part 4)




EASTNORTHEAST - This is not exactly the hint Jim Sanborn (JS) gave for K4 on the 29th of January this year. He only gave NORTHEAST - which refers to the positions 26-34 of K4's plaintext.  Beside BERLIN and CLOCK it is the third revealed plaintext word of K4. However, also this hint does not seem to help much. 

However, it just so happened, that a member in the yahoo kryptos group had a conversation with Jim Sanborn due to a submitted solution. Sandborn's answer to the question contained again the last clue which surprisingly was EASTNORTHEAST at position 22-34. There is disagreement if Jim revealed this on purpose or he did it accidentially, but the new extended clue seem to be serious and valid. 

Interestingly, EASTNORTHEAST is exactly the direction which is illustrated on the
wind rose on one of the stones around kryptos, also created by Jim Sanborn.


Below you can see that new hint at the position in the plaintext:

                                                       O B K R 
 U O X O G H U L B S O L I F B B W E A S T N O R T H E A S T
T W T Q S J Q S S E K Z Z W A T J K L U D I A W I N F B B E R
L I N C L O C K W G D K Z X T J C D I G K U H U A U E K C A R