Magic Square and Cryptography (Developments of Language, Logic, Algebraic system and Computer Science)

(1)

Magic Square

and

_Cryptography

Tomoko

_Adachi,

Yohei

_Sugita

Department

of Information

_Sciences,

Toho

_University

2‐2‐1

_{Miyama, Funabashi, Chiba,}

_274‐8510,

_Japan

E‐mail:

_{adachi@is.sci.toho‐u.ac.jp}

1. Introduction

A

_magic

_squareof ordern isan

_arrangement

of the

n^{2} integers

0,

1,

\cdots,

n^{2}-1

into an n\times n _square with the

_property

that the sums of each _row, each

column,

and eachof the main

_diagonals

arethesame.

Magic

_squares areknown in ancient

times in China and India.

_{Many people}

have been interested in

_magic

_squares for hundreds _years.

In this paper, we describe relation of

magic

_squares and latin _squares. More‐

over, we described

_cryptosystem

basedon

magic

_squares.

2.

_{Magic Square}

and Latin

_Square

A latin _square oforder n is an n\times n _array in which n distinct

symbols

are

arranged

sothat each

symbol

occursonce ineach row and column.

Let

_{L_{1}}

and

_{L_{2}}

be latin_squares of thesame order

n(\geq 2)

. Wesaythat

L_{1}

and

L_{2}

are

orthogonal if,

when

superimposed,

each of the

_{possible n^{2}}

ordered

_pairs

occurs

exactly

once. We say that a set

\{L_{1}, L_{2}, \cdots, L_{t}\}

oft

(\geq 2)

latin _squares

of order n is

orthogonal

if _{any two} distinct _squares are

orthogonal.

Such a set

of

_orthogonal

_squares is said to be a set of

_{rnutually orthogonal}

latin _squares

(MOLS).

For

_{q\geq 5}

an odd

prime

_power, aset of

_q-3

MOLS of order q eachof which has distinct elements on the two main

_diagonals.

Such latin _squares aresaid to

be

_diagonal.

Theorem 2.1

_(Ỉ21)

_If

n is an

integer

for

which thereis a

pair

of orthogonal diag‐

onal latin_squares

_of

ordern, then a

magic

square

of

ordern can be constructed.

Example

2.2 Let consider the

_{following orthogonal diagonal}

latin _square of order 5.

数理解析研究所講究録

(2)

4 2 1 0 3 0 3 4 2 1

L_{1} = 2 1 0 3 4

3 4 2 1 0 1 0 3 4 2 4 0 2 1 3 2 1 3 4 0

L_{2}

= 3 4 0 2 1 0 2 1 3 4 1 3 4 0 2

If

_{L_{1}}

is

_superimposed

on

L_{2}

_,weobtain the

following

_array

L_{1}L_{2}

of ordered

pairs.

Ifwe consider an ordered

pair

in each cellof

L_{1}L_{2}

as a

_pentanary

number,

and we

change

a

_pentanary

number in each cell of

L_{1}L_{2}

into a

denary

number,

we

obtain the

_magic

square M of order 5. 44 20 12 01 33 02 31 43 24 10

L_{1}L_{2}

= 23 14 00 32 41 30 42 21 13 04 11 03 34 40 22 24 10 7 1 18 2 16 23 14 5 M = 13 9 0 17 21 15 22 11 8 4 6 3 19 20 12

3.

_Cryptosystem

Based on

Magic Square

In this

_section,

we described

cryptosystem

based on

magic

_squares

([1]).

At

_first,

we _prepare a 4

digits

seed

number,

a

starting

number of a

magic

square, and a

magic

_square sum, The

algorithm

of

[1]

starts with

building

4\times 4

magic

square,

by using

a

_starting

number anda

_magic

_squaresum.

Incrementally,

8\times 8 and 16\times 16

_magic

_squares arebuilt

_using

4\times 4

_magic

_squares as

building

blocks. Ifwe have a _{message with} t

_letters,

we build t16\times 16

_magic

_squares.

Secondly,

we

investigate

theASCIIvalue of each letter ina_message.

Suppose

that we have a _{message ABA} The ASCII values offor \mathrm{A} and B are 65

and

_{66, respectively.}

To

_encrypt

(\mathrm{A}

_,

the numerals whichoccur at65‐th

_position

infirst and third 16\times 16

_magic

_squares aretaken. To

_encrypt

\mathrm{B}

,

the numeral

which occurs at 66‐th

position

in second 16\times 16

magic

_square is taken. When we

_encrypt

a _message, we use a

public‐key

_cryptosystem

RSA.

Then,

the first

and third letters Aare

_encrypted

different

_cipher

_texts, since we use different

16\times 16

_magic

_squares.

References

[1]

G.

_Ganapathy,

and K.Mani

_(2009);

Add‐On

_Security

Model for

_Public‐Key

Crtptosystem

Based on

Magic Square Implementation, Proceedings of

the

World

_Congress

on

Engineering

and

Computer

Science 2009 Vol. WCECS

2009,

October

_{20‐22, 2009,}

San

_Francisco,

USA

(3)

[2]

C. $\Gamma$.

Laywine

and G. L. Mullen

(1998);

Discrete Mathematics

Using

Latin

Squares,

John

_Weiley

&

_Sons,

INC.