Veri Sıkıştırma – Huffman Algoritması – JS

 
 
 var sozluk=[];
 
function print(a){
	$("#out").html($("#out").html()+a);
}
function clone(oldObject){
	return jQuery.extend({}, oldObject);
}
 
$("#buton").click(function(e){
	calc();
});
 
 
function Node(ust,left,right,level,frekans,char){
	this.ust = ust;
  this.left = left;
  this.right = right;
  this.level = level ;
  this.char = char;
  this.frekans = frekans;
  this.kod="";
}
 
function calc(){
  var text = $("#tb").val();
  var array = text.split("");
  var chars = [];
  var frekans = [];
  var sorted = [];
 
	$("#out").html("Toplam : "+array.length+"<h2>Frekanslar</h2>");
 
  for(k in array){
    if(chars.indexOf(array[k]) == -1)
      chars.push(array[k]);
  }
 
  for(k in array){
      ch = chars.indexOf(array[k]);
      if(ch != -1){
        if(frekans[ch]){
          frekans[ch]++;
        }
        else
        {
          frekans[ch]=1;
        }
      }
  }
 
  for(i in chars){
    print("'"+chars[i]+"' "+( frekans[i]/array.length)+"<br>" );
    sorted.push({
    	"char" : chars[i],
      "frekans" : (frekans[i]/array.length)
    });
  }
 
 
  var levels=[[]];
 
  for(i=0;i<sorted.length;i++){
  		levels[0].push(new Node(false,false,false,0,sorted[i].frekans,sorted[i].char));
  }
 
  var level = 0;
  while(levels[level].length>2){
 
    levels[level].sort(function(a, b) {
    	return parseFloat(b.frekans) - parseFloat(a.frekans);
		});
 
    level++;
    levels.push([]);
 
    i = levels[level-1].length-1;
 
    levels[level].push(new Node(false,levels[level-1][i-1],levels[level-1][i],level,(levels[level-1][i-1].frekans+levels[level-1][i].frekans),"yok"));
 
    levels[level-1][i-1].ust = levels[level][levels[level].length-1];
    levels[level-1][i].ust = levels[level][levels[level].length-1];     
 
		for(var j = levels[level-1].length-3 ; j>=0;j--){
      	levels[level].push(levels[level-1][j]);
        levels[level-1][j].ust = levels[level][levels[level].length-1];
    }
 
 
  }
 
   levels[level].sort(function(a, b) {
    	return parseFloat(b.frekans) - parseFloat(a.frekans);
	});
 
 
 
  GenerateCode(levels[level][0],"1");  
  GenerateCode(levels[level][1],"0");
 
 
 
 
 
 
 
  print("<h2>Ağaç</h2>");
 
 
 
  levels.forEach(function(e){
  	print("<br>");
    e.forEach(function(l){
    	print(Math.round(l.frekans*100)/100+" | ");
    })
  });
 
    print("<h2>Kod</h2>");
 
 
 
  levels.forEach(function(e){
  	print("<br>");
    e.forEach(function(l){
    	print(l.kod+" | ");
    })
  });
 
  sozluk=[];
 
  print("<h2>Kodlama</h2>");
      levels[0].forEach(function(l){
    	print(l.char+" = "+l.kod+" <br> ");
      sozluk.push({
      	"char" : l.char,
        "kod" : l.kod
      });
    })
 
  print("<h2>Encode</h2>");
 
  array.forEach(function(e){
  	print(encode(e));
  });
 
  console.log(levels);
 
 
}
 
 
function GenerateCode(node,kod){
  	node.kod=kod;
    if(node.left)
  		GenerateCode(node.left,"1"+node.kod);  	
    if(node.right)
    	GenerateCode(node.right,"0"+node.kod);
}
 
function encode(char){
  for(k in sozluk){
  	if(sozluk[k].char==char)
    	return sozluk[k].kod;
  }
  return "?";
}

Kriptoloji

Kriptoloji (Şifreleme Bilimi)

  1. Kriptografi : Şifreleyerek bilgilerimizi gizlemektir.
  2. Kriptoanaliz : Başkaların şifreli metinlerini inceleyerek, metni elde etmektir

Encode : Farklı formata dönüştürme. Utf8 -> Base64,Hex

Plaintext P: Metin

Ciphertext C: Şifrelenmiş Metin

Key K: Şifreleyen anahtar. Şifre

Cipher : Şifreyici

Encrypt : Metni şifreleme fiili

Decrypt : Şifrelenmiş metni çözme fiili ( – deşifre )

Base64 : Verilerin 2^6 lik, 64 karakterle ifadesini sağlar. Bu biçimi binaryler ve ASCIIler çevrilebilmektedir. Genelde sonlarında = veya == bulunur. Herkes tarafından bilinir ve encoding/decoding yapılabilir.

Kerckhoff Prensibi

Bir kripto sisteminin güvenliği algoritmayı gizli tutmaya bağlı olmamalıdır. Sadece Key’in gizliliğini bağlı olmalı. Çünkü algoritmayı değiştirmek zordur.

XOR

Farklı olma durumu arayan kapıdır. 00=0 , 01=1 , 10=1 , 11=0

A xor B = A
A xor A = 0
A xor B xor A = B

Son kısma dikkat ; P xor K xor K = P oluyor. Yani XOR ile şifrelemede Key iki defa kullanılamaz.

P1 xor K = C1
P2 xor K = C2

olsun.  O zaman

C1 xor C2 = P1 xor P2

Yani Şifrelenmiş iki metni’nin xor, Şifrelenmemiş hallerinin iç içe geçmiş hali olacaktır. Eğer bunu bir resimde yapsaydık, iki resmi içi içe görürdük.

OTP (Vernam)

One-time pad (Tek kullanımlık Şerit): P xor K = C ‘nin tektek her bit için kullanıldığı. P ve K şeritlerini alıp C şeridi veren şifreleme türüdür. Sadece bir defa kullanılmalıdır. Kırılmasının imkansız olduğu kanıtlanmıştır. Anahtar üretme ve dağıtma zorluğu vardır.

Rastgelelilik

Rastgelelilik bir teoridir. Birşeyin rastgele olmasının sebebi, onu hesaplayamamız veya nasıl hesaplanacağını bilmemizdir.

Pseudo Random Number Generator : 

Bu algoritma mod fonksiyonun geri döndürülemezlik özelliğini kullanır.

Xi+1 = (a.Xi+c)modM;

Bu C’dilin random sayı üretme algoritmasıdır. a ve c sabit değerdir. (asal sayı olması önerilir) Xi önceki random üretilen sayıdır. M ise aralık boyutudur.

Sezar Şifreleme

@monoalphabetic chiper family

P : abcd
C : bcda
K : 1

Karakterleri alfabede K sonraki harfe kaydırarak şifrelemedir.

Cn = (Pn+K)mod(HarfSayısı)
  • Harfleri frekansı(sıklığı) ölçülerek kolayca çözülebilir. Ö : Türkçede en fazla A harfi kullanılır. İngilizcede ise E harfi kullanılır. Bu bilgi dilin son yayılanan makalelerindeki harfler sayılarak elde edilebilir. Metin ne kadar uzunsa , bu yöntemle çözülmesi o kadar kolaydır.
  • Kaba Kuvvet ile Harf Sayısı kadar şifre olasılığı (ö : 29) deneyerekte çözülebilir.

Simetrik Şifreleme

Tek bir anahtar ile , hem şifreleme hemde deşifreleme işlemi yapmaktır.

DES (Veri şifreleme standartı)

Herkesin bilebildiği, şifrenin gizliliğine dayalı , IBM tarafından üretilenen bir standart simetrik algoritmadır.  Key 56 bit sabittir.

  • Permutasyon fonksiyonu ile yer değiştirme yapılır. Bu yüzden metinden bir bit bile değişirse, şifreli metnin neredeyse tamamı değişir.
  • Metin ikiye bölünür.(sol,sağ) Keyden subkeyler üretilir. Sağ taraf, subkey ile F fonksiyonuna yönlendirilir. F fonksiyonu, sol taraf ile xor’lanır. Sonraki aşamada XOR’lanmış değer sağ taraf, F fonksiyonun sol taraf olur. Bu işlem 16 defa yapılır.
  • Rivayet: Artık kullanımı iptal edilmiştir. Güvensizdir. Çünkü : Deşifrelemede, key’e bir bit yaklaşılırsa. Metinin yarısı çözülür.
  • 99da 22 saat 15 dakikada kırılabilmiştir. (Metin : Romada görüşürüz. Herkes AES kullansın.)
  • DES’in açığı bilerek bırakılmamıştır. O dönemde güçlü olduğu düşünülüyordu. (1977)

AES (Gelişmiş şifreleme standartı)

Joan Daemen ve Vincent Rijmen adlı 2 belçikalı bulmuştur. Romadaki AES yarışmasında birinci olmuştur. (15 algoritmadan) Asıl adı : RIJNDAE

  • AES, 2000 yılında çıktı. Keyler 128,196 ve 256 bittir. Blok boyutu 128 bittir.

RC4

40-2048 bit key sahibi, 256 roundlik bir şifreleme biçimidir.

Asimetrik Şifreleme

Şifrelemek için ayrı şifre, şifrelemiş metini çözmek için ayrı şifre gerek şifreleme biçimidir.

RSA

Asal sayıların kullanıldığı asimetrik şifreleme algoritmasıdır.

CBC modu

iv (initialization vector) : başlangıç vektörü. şifreleme algoritması için gerekli olan başlangıç bilgisidir.(gizlenmelidir) 0. bloktan sonrakiler için gerekmemekte.

CFB modu

Kendini feedbackleyen moddur.

Hash

Veriyi özetlemek, doğruluğunu kontrol etmek için kullanılan fonksiyondur. Geri döndürülemez olmamalıdır. Adli işlerde , kanıtların doğruluğunu ve değiştirilmedini kanıtlamak için kullanılır. Hep sabit uzunlukla çıktı verir.

md5

popüler ve hızlı hash algoritmasıdır. Sözlük saldırısı ile geri döndürebilme ihtimalı vardır. md5(“dsadas”.text) ile tuzlama yapılarak bundan korunulabilmektedir.