Wednesday, October 12, 2022

Kryptos - The Cipher (Part 5)

ONE of the most surprising fact about Kryptos is, that nobody has yet discovered the anticipated way the keywords for K1 und K2 should be found. And maybe this missing fact is the key why we are stuck with K4. I don't think, that Sanborn wanted us to bruteforce the solutions (as we did), but somehow left a hint we didn't recognized so far.

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 granit with contained copper plates. I found two very interesting drawings of these two installations from Monet Friedrich on [1]:



Monday, November 02, 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
 

Friday, March 27, 2020

Factoring via perfect matchings in an n-bit multiplier graph

Factoring integers is a well studied topic in mathematics and computer science. The number of approaches to this problem numerous. There are even some graph related approaches to this problem. One particular, but not very efficient way, which i also covered in a previous blog post, is to convert an integer to a 3-USAT formula and find the unique satisfying assignment. I never heard of an approach that converts the integer factorization problem to a perfect matching problem.
Main Goal. What we want to accomplish with our approach is to build a planar graph $\mathcal{G}$ that reassembles an $n$-bit multiplier. $\mathcal{G}$ should be build in a way that it has exactly one perfect matching (or some derived graph has a perfect matching) and this perfect matching reveals the factorization of the given product $pq$.
One way to realize multiplication of two $n$-bit numbers $p$ and $q$ in hardware is to build a network of cascading $n^2$ adder gadgets. Such a construction is called an $n$-bit multiplier and has $2\times n$ input nodes that are assigned with the $2\times n$ bits of the two input numbers $p$ and $q$. Consequently, it also has $2\times n$ output nodes that represent the $2\times n$ bits of the final product $pq$. Each of the involved $n^2$ adder gadgets has $4$ input and $4$ output nodes and is illustrated in Figure 1.

Figure 1 - An adder gadget with 4 input and 4 output nodes. Two nodes with the same color represent a pair of input and output nodes, i.e., the green $p_i$ in the input area gets the input of the $i$-bit of the input integer $p$ and the green node in the output area simply outputs the same bit  and hands it over to the next adder gadget.

The meaning of the different colors in the figure are:
  1. GREEN $p_i$: The $i$-th bit of the input integer $p$
  2. RED $r$: The result output of an previous adder gadget
  3. YELLOW $q_i$: The $i$-th bit of the input integer $q$
  4. WHITE $c_{in}$: The carry output of an previous adder gadget.
An $n$-bit multiplier is an arrangement of the these $n^2$ adder gadget as shown in Figure 2 for the case $n=3$.
Figure 2 - $3$-bit multiplier with $9$ adder gadgets.

Monday, January 28, 2019

Factoring using BQF (not SQUFOF)

We start with a very brief primer to Binary Quadratic Forms (BQF). For more information ⦗1⦘ is a very good source to start with.

 A Binary Quadratic Form is a polynom of the form $Q(x,y) = ax^2+bxy+cy^2$ with integer coefficients. We focus on integer BQF, i.e., $x,y \in \mathbb{Z}$. Often one is only interested in the behaviour of the coefficients $a,b,c$ and in those cases one refers to a BQF simply by the triple $(a,b,c)$. Further, the integer $D$ defined as: $$D = b^2 - 4ac$$ is called the discriminant of $(a,b,c)$.

 A positive definite BQF $(a,b,c)$, i.e. $D < 0, a > 0$, is reduced if $-a < b < a < c$. Gauss observed, that all reduced BQF with the same discriminant form an abelian group and he gave a composition algorithm for those group elements. This group is called the class group and is usually denoted as $\mathcal{Cl}(D)$. The size of the group has a special name and is called the class number $h(D)$. Informally spoken, the class group $\mathcal{Cl}(D)$ contains all different reduced quadratic forms with the same discriminant $D$.