Visual Kriptografi Wu ve Chen in Şeması

Merhaba,

Wu ve Chen adlı 2 araştırmacı 1998 yılında (2,2) lik yeni bir Visual Secret Sharing metodu önerdiler. Bu önerilen metoda göre herhangi 2 tane gizli görüntü döndürme teknikleri kullanılarak 2 Share in içerisine gömülebilir. Kullanılan döndürme açıları genellikle 90,180 ve 270 derece olmakla beraber shareler de karesel bir formata sahip olurlar. Karesel biçimde olmalarının sebebi pixellerin birbirleriyle birebir örtüşmek zorunda olmalarındandır.

2 tane NxN boyutunda halftone görüntü 2Nx2N lik share ler oluşturmak üzere her pixel 4 alt pixelle temsil edilecek şekilde genişletilir. Bu 4 alt pixele 2×2 lik genişletilmiş blok denir. Oluşturulan bu shareler gizli görüntü hakkında bilgi vermez. Diğer yandan ilk gizli görüntünün elde edilmesi için ilk iki share üst üstte pixelleri birebir örtüşmek şartıyla getirilerek elde edilir. İkinci gizli görüntünün elde edilmesi için ise ilk share 90^o saat yönünün tersine döndürülüp ikinci share ile üst üste getirildikten sonra elde edilir. Wu ve Chen in algoritmasına göre ilk share aşağıdaki gibi 4 tane eşit üçgensel bölgeye ayrılır.

İlk share in birinci bölgesinde bulunan her bir 2×2 lik genişletilmiş bloklar aşağıdaki pattern kümesi içerisinden rastgele olarak seçilmesiyle elde edilirler.

 

Diğer 3 bölgedeki patternlerin atanması işlemi ilk bölgeyle aynıdır. Wu ve Chen ilk share i eşit içeriğe sahip 4 üçgensel bölgeye ayırır. Böylece her bir bölge (NxN)/4 tane genişletilmiş blok içerir.Her bir Üçgensel bölgedeki genişletilmiş bloklar aynıdır.İlk bölgedeki genişletilmiş bloklar rastgele seçilmekte ve diğer bölgelerde o noktaya karşı düşen koordinata da aynen kopyalanmaktadır.Bu işlem aşağıda gösterilmiştir.

 

İkinci share in genişletilmiş blokları ise ilk share in genişletilmiş bloklarına göre belirlenmeli ve pixel renk değeri ise Secret görüntü üzerinde ilişkili noktaya göre belirlenir. Wu ve Chen in şemasının çalışma prensibi bir örnekle daha net açıklanacaktır.

Anlatılacak örnekte Secret görüntüler sırasıyla P₁ ve P₂ ile temsil edilecek ve oluşturulacak Shareler ise S₁ ve S₂ ile ifade edilecektir. Öte yandan İlk share in 90^o saat yönünün tersine döndürülmesiyle elde edilecek olan Share ise S₁^o ile temsil edilecektir.

 

Basit olması açısından verilen örnekteki Secretların büyüklükleri 6×6 olacaktır. Böylece Share lerin büyüklükleri de 12×12 olacaktır.Yukarıda belirtildiği gibi ilk share 4 eşit üçgensel bölgeye ayrılacaktır yani ilk share 9 tane genişletilmiş bloktan oluşan 4 üçgensel bölgeye sahip olacaktır.Aşağıda her bir bölgenin blok içerikleri numaralandırılmış olarak verilmiştir. Böylece her bölgenin ilişkili blokları daha rahat incelenebilecektir.

Yukarıdaki şekilde birbirleriyle ilişkili olan genişletilmiş blokların içerikleri aynıdır. Aşağıda verilen şekilde Secret1,Secret2 ve Share1,Share2,Share1’ gösterilmiştir. Pixel değerlerine dikkat edilecek olursa aynı numaralı içeriklerin birbirine eşit olduğu görülmektedir.

 

 

Örneğin; Secretların (0,2) kordinatında ki pixelleri incelersek sırasıyla , dır. İlk share random olarak belirlendiği için şekilde görüldüğü gibi (0,2) noktasındaki Genişletilmiş blok değerini almıştır. Bununla beraber bu genişletilmiş bloğun ilişkili dönmüş değeri (3,0) da bulunan değeri olacaktır. Aynı şekilde ilişkili genişletilmiş bloklarda dönmüş Share de aynı değerleri alacaktır. Böylece İlk share random bir şekilde seçilecek ve buna denk düşen 90^o saat yönünün tersindeki kordinata dönmüş pattern yerleştirilecektir.

 

Secret 1 in belirtilen değeri beyaz olduğu için Share1 in değeriyle Share 2 inin belirlenmemiş genişletilmiş bloğu üst üste geldiğinde beyaz değerini vermesi gerekir. Bu yüzden Share 2 inin değeri aşağıdaki pattern kümesi arasından seçilmesi gerekir.

Bu beyaz görünümlü patternler arasından ilk share in değeriyle üst üste geldiğinde beyaz görünüm verecek olan patternler aşağıdaki patternlerdir.

Share 2 nin ilişkili değerine baktığımız zamanda bu 2 patternden birisi random olarak patterni belirlenmiştir.

Aşağıdaki şekilde Share 1 in 90 derece dönmesiyle oluşan genişletilmiş blokların pozisyonları verilmiştir. Bu şekilde Share in ve dönmüş share in ilişkili pixeli rahatlıkla takip edilebilir.

 

Yukarıdaki şekilde,a₁ ile gösterilen seçilmiş patterni resmeden(boyayan) genişletilmiş blok ,ilk share in oluşu boyunca a₃₁ diye resmedilen(boyanan) genişletilmiş bloğunun pattern seçimini etkiler.Aslında her adımda bu 4 genişletilmiş bloğun pattern seçiminde bağımlılıklar veya sınırlamalar vardır.Örneğin ilk adım için a₁,a₃₁,a₆ ve a₃₆ nolu bloklar hem ilk share de hem de döndürülmüş share de gerekli pattern kümesi belirtilen sınırlamalarla belirlenecek ve bunların içerisinden random olarak seçilecektir.

Bağımlılıklar ve sınırlamaları belirtme açısından şöyle bir örnek verilebilir. Genişletilmiş bloklardan a₁ ve a₆ random bir şekilde seçilirse,ve Secret görüntülerin ilk pixelleri sırasıyla olursa, a₆ nın döndürme sonucu olan patterni , a₁ in ilişkili genişletilmiş bloğu olacaktır.

 

Bu yüzden S1 ve S1^o in genişletilmiş blokları şeklinde olur. Bu durumda,S2 ye gelecek uygun genişletilmiş blok için gerekli pattern bulunmayacaktır.

S2 patternlerinden iki genişletilmiş blok arasında haming uzaklığı 0 olan hiçbir pattern, bu genişletilmiş bloklarla üst üstte getirildiği zaman iki secret görüntünün pixel değerlerini şeklinde göstermeyecektir.

Hamming uzunlukları ya 1 yada 2 olmak zorundadır çünkü patternlerin ikinci share i oluşturan hamming ağırlıkları 2 dir. Hamming uzunluğu 1 olamaz çünkü birinci share i meydana getirecek olan bütün patternler 3 siyah pixele ve 1 beyaz pixele sahiptir. Döndürmeden dolayı bir pixelde ki fark, hamming uzunluğunun 2 olmasıyla sonuçlanacaktır.

 

 

Wu ve Chen in Algoritması, a₁,a₃₁,a₆ ve a₃₆ olmak üzere bu 4 genişletilmiş bloğu boyayabilmek için aynı pattern i seçerler.Wu ve Chen in Şemasına başvurulduğunda, a₁ ve a₆ yı resmetmek(boyamak) için aynı pattern kullanılacaktır.Eğer a₁ ve a₆ şeklinde seçilirse,S1 ve S1^o deki ilişkili genişletilmiş bloklar şeklinde olacaktır.

Herhangi bir S2 patterni,S2 deki ilişkili genişletilmiş blok için seçilirse, bu 2 genişletilmiş blok arasında ki hamming uzaklığı 2 olacaktır.İlişkili bloklar arasında ki hamming uzaklığı her zaman 2 olacaktır çünkü genişletilmiş bloklar döndürülmüş resimde ki bloklarla örtüşecektir. Pixel değerlerinin bütün kombinasyonları uygun S2 pattern ini seçerek kodlanır.

 

Yukarıda ki örnekte de görüldüğü gibi, Wu ve Chen ilk share görüntüyü içeriği eşit olacak şekilde 4 tane üçgensel bölgeye ayırmaktadırlar.S1 deki genişletilmiş bloğun döndürülmüş pattern i ve aynı şekilde 90^o saat yönünün tersine döndürülmüş S1 in genişletilmiş blokları aynı olmak zorundadır ve genişletilmiş blok pattern i rotasyonla örtüşen bütün genişletilmiş bloğa kopyalanır. Bunu k=1 durumu için şeklinde ve k=2,3,4 değerleri içinde şeklinde olur.

 

Sonuç olarak,Wu ve Chen in algoritmaları rotasyonla gelen genişletilmiş bloklar için örtüşmelerde aynı patternlerin kopyalanmasıyla birlikte genişletilmiş bloklar arasında ki bağımlılıkları yada sınırlamaları dikkate almaya gerek bırakmayacaktır. Wu ve Chen in metotlarında ilk share in yani S1 in rastgele olmayan sınırından dolayı görünmeyen bir tehlike vardır.Her bir üçgensel alanda ki ilişkili pixeller aynı değere atanmalarına karşın,ilk share yani S1 tam olarak random değildir.Sadece ilk share in ¼ ü randomdur ve geriye kalan ¾ lük alan ise ilk üçgensel bölgenin tam bir kopyasıdır.