PDA

View Full Version : فشرده سازی رشته رمز نگاری شده توسط الگوریتم هافمن



negar.rafie
یک شنبه 19 شهریور 1391, 23:50 عصر
سلام دوستان
من برای رمزنگاری اطلاعات از الگوریتم AES استفاده می کنم ولی به عنوان مثال اگر حرف a را رمزنگاری کنیم رشته رمزنگاری شده به صورت زیر خواهد بود :
Z+++c3ZSdlfmzLIX8SOR+A==
که خیلی طولانی و اگر بخواهیم یک جمله را رمزنگاری کنیم رشته تولید شده بسیار طولانی است
حالا برای اینکه طول رشته را کمتر کنیم باید ان را با الگوریتم هافمن فشرده کنیم ولی من نمی تونم با الگوریتم هافمن کار کنم
حالا من کلاس الگوریتم AES را میزارم اینجا لطفا بگید بعد از رمز نگاری با الگوریتم AES چطور رشته تولید شده را فشرده کنم

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;
using System.IO;
namespace Algorithm_AES
{
public class AES
{

public AES()
{
}

private byte[] Encrypt(byte[] clearData, byte[] Key, byte[] IV)
{

MemoryStream ms = new MemoryStream();

Rijndael alg = Rijndael.Create();
alg.Key = Key;

alg.IV = IV;
CryptoStream cs = new CryptoStream(ms, alg.CreateEncryptor(), CryptoStreamMode.Write);

cs.Write(clearData, 0, clearData.Length);
cs.Close();
byte[] encryptedData = ms.ToArray();
return encryptedData;
}


public string Encrypt(string Data, string Password, int Bits)
{

byte[] clearBytes = System.Text.Encoding.Unicode.GetBytes(Data);

PasswordDeriveBytes pdb = new PasswordDeriveBytes(Password,

new byte[] { 0x00, 0x01, 0x02, 0x1C, 0x1D, 0x1E, 0x03, 0x04, 0x05, 0x0F, 0x20, 0x21, 0xAD, 0xAF, 0xA4 });

if (Bits == 128)
{
byte[] encryptedData = Encrypt(clearBytes, pdb.GetBytes(16), pdb.GetBytes(16));
return Convert.ToBase64String(encryptedData);
}
else if (Bits == 192)
{
byte[] encryptedData = Encrypt(clearBytes, pdb.GetBytes(24), pdb.GetBytes(16));
return Convert.ToBase64String(encryptedData);
}
else if (Bits == 256)
{
byte[] encryptedData = Encrypt(clearBytes, pdb.GetBytes(32), pdb.GetBytes(16));
return Convert.ToBase64String(encryptedData);
}
else
{
return string.Concat(Bits);
}
}


private byte[] Decrypt(byte[] cipherData, byte[] Key, byte[] IV)
{

MemoryStream ms = new MemoryStream();
Rijndael alg = Rijndael.Create();
alg.Key = Key;
alg.IV = IV;
CryptoStream cs = new CryptoStream(ms, alg.CreateDecryptor(), CryptoStreamMode.Write);
cs.Write(cipherData, 0, cipherData.Length);
cs.Close();
byte[] decryptedData = ms.ToArray();
return decryptedData;
}


public string Decrypt(string Data, string Password, int Bits)
{

byte[] cipherBytes = Convert.FromBase64String(Data);

PasswordDeriveBytes pdb = new PasswordDeriveBytes(Password,

new byte[] { 0x00, 0x01, 0x02, 0x1C, 0x1D, 0x1E, 0x03, 0x04, 0x05, 0x0F, 0x20, 0x21, 0xAD, 0xAF, 0xA4 });

if (Bits == 128)
{
byte[] decryptedData = Decrypt(cipherBytes, pdb.GetBytes(16), pdb.GetBytes(16));
return System.Text.Encoding.Unicode.GetString(decryptedDa ta);
}
else if (Bits == 192)
{
byte[] decryptedData = Decrypt(cipherBytes, pdb.GetBytes(24), pdb.GetBytes(16));
return System.Text.Encoding.Unicode.GetString(decryptedDa ta);
}
else if (Bits == 256)
{
byte[] decryptedData = Decrypt(cipherBytes, pdb.GetBytes(32), pdb.GetBytes(16));
return System.Text.Encoding.Unicode.GetString(decryptedDa ta);
}
else
{
return string.Concat(Bits);
}

}

}
}

negar.rafie
دوشنبه 20 شهریور 1391, 08:54 صبح
اینم پروژه

negar.rafie
دوشنبه 20 شهریور 1391, 12:20 عصر
مثل اینکه دوستان و اساتید از سوالات زیادی که من میکنم ناراضی شدند ولی به خدا قسم من قبل از تاپیک زدن سایت برنامه نویس و اینترنت را میگردم و اگر به جواب سوالم نرسیدم تاپیک میزنم
حالا یکی از کاربرها پیام داده که متن پیام به این صورته:
شما توی این سایت بیشتر مصرف کننده اید و منم خوشم نمیاد اگر توی توان باشه به اینجور آدما کمک کنم هر چند وجدان...یه خورده حس انسان دوستانتون رو حرکت بدید.
من تازه اومدم تو این سایت حالا فکر نکم با وجود اساتید من بخوام جواب بدم منظورم این نیست که کاربرهایی مثل من اصلا جواب ندن نه یعنی باید یکم از سابقه افراد در سایت بگزره بعد
شما تاپیکهای من را ببینید اکثرا برای دیگران هم مفید بودن
حالا باشه اگر اساتید ناراحت هستند دیگه سعی می کنم تاپیک نزنم
خدانگهدار

Arash_janusV3
دوشنبه 20 شهریور 1391, 12:46 عصر
مثل اینکه دوستان و اساتید از سوالات زیادی که من میکنم ناراضی شدند ولی به خدا قسم من قبل از تاپیک زدن سایت برنامه نویس و اینترنت را میگردم و اگر به جواب سوالم نرسیدم تاپیک میزنم
حالا یکی از کاربرها پیام داده که متن پیام به این صورته:
شما توی این سایت بیشتر مصرف کننده اید و منم خوشم نمیاد اگر توی توان باشه به اینجور آدما کمک کنم هر چند وجدان...یه خورده حس انسان دوستانتون رو حرکت بدید.
من تازه اومدم تو این سایت حالا فکر نکم با وجود اساتید من بخوام جواب بدم منظورم این نیست که کاربرهایی مثل من اصلا جواب ندن نه یعنی باید یکم از سابقه افراد در سایت بگزره بعد
شما تاپیکهای من را ببینید اکثرا برای دیگران هم مفید بودن
حالا باشه اگر اساتید ناراحت هستند دیگه سعی می کنم تاپیک نزنم
خدانگهدار

درود بر شما
برای پیدا کردن جواب مسائل راههای بسیار زیادی وجود داره
در این سایت و مطرح کردن مسئله یکی از راههاست
شما باید برای رسیدن به جوابتون همه راهها را پیش بگیرید
قرار نیست همه همزمان کمک کنند اگر اینطوری باشه پس کی سوال مطرح کنه ؟
به نظر من همین سوالها و جوابهاست که این سایت رو به مرجع کامل فارسی زبان تبدیل کرده
از حرفهای دیگران هم ناراحت نشید شما سوالتون رو مطرح کنید حالا یا جوابی هست یا نیست
کمک کردن اختیاری هستش اما متاسفانه بعضی ها براساس تشکر گرفتن کمک می کنند
یا بعضی ها طرف مقابل رو در نظر می گیرند بعد کمک می کنند
اما شما ناراحت نشید البته خیلی از دوستان از چنین موضوعات ناراحت می شند
مهم نیست به کار خودتون ادامه بدید
موفق باشید

amir11205
جمعه 24 شهریور 1391, 08:15 صبح
سلام
یه سر به لینک زیر بزن.
ببین کارت راه میوفته یا نه؟
کدش تقریبا واضحه اما اگه بازم نفهمیدی بگو
http://snipd.net/huffman-coding-in-c

amir11205
شنبه 25 شهریور 1391, 09:55 صبح
سلام
این هم برنامه خودتون با الگوریتم هافمن

negar.rafie
شنبه 25 شهریور 1391, 10:15 صبح
خیلی ممنون اقا امیر
حالا یه سوال ما مثلا حرف a را رمزنگاری کردیم شد:
Z+++c3ZSdlfmzLIX8SOR+A==
بعد عبارت رمزنگاری شده را فشرده کردیم شد :
10101001001001101011011101010111110011101111101111 100000001001000110100101101010110100011111001100

ما میخواستیم فشرده کنیم که حجم و تعداد حروف بیاد پایین ولی وقتی فشرده کردیم بیشتر شد که
مشکل کجاست

amir11205
شنبه 25 شهریور 1391, 10:29 صبح
خواهش میکنم
شما نباید اون صفر و یک ها رو کاراکتر در نظر بگیرین
بلکه اونا همه بیت هستن (اگه تو کد برنامه دقت کنین کلمه BitArray رو میبنین که هم نوع پارامتر خروجی انکد کردن و هم پارامتر وروردی دیکد کردن هستش)
اگه دقت کنین تعداد اون صفر و یک ها 98 تاست که که اگه بر 8 (اندازه بایت) تقسیم کنین حدود 12 بایت میشه
اما رشته Z+++c3ZSdlfmzLIX8SOR+A== شامل 24 کاراکتره که حداقل 24 بایت فضا رو اشغال می کنه و این یعنی ما با هافمن تونستیم حجمو کاهش بدیم

negar.rafie
شنبه 25 شهریور 1391, 10:36 صبح
حالا نمیشه با هافمن کاری کرد که علاوه بر حجم تعداد کارکترها هم کمتر بشه؟

amir11205
شنبه 25 شهریور 1391, 10:53 صبح
اصل روش هافمن بر فراوانی کاراکترها استواره و فقظ هدفش کاهش حجمه
در واقع هافمن میاد به کاراکترهای با تکرار زیاد طول بیتی کمتر اختصاص میده و مسلما وقتی کاراکتر با تکرار زیاد طول بیتیش کم باشه حجم کل رو کاهش میده و بیت ها رو با کارکتر مورد نظر جایگزین میکنه و خبری از حدف کاراکتر نیست.
هدف شما از فشرده سازی چیه؟
کاهش حجم خروجیه یا نه فقط جلوگیری از تکرار کاراکترهاس؟
اگه هدف کاهش حجمه که یک الگوریتم کارآمد برای فایل های متنی همین هافمنه اما اگه هدف جلوگیری از تکرار کاراکترهاس که به نظر من باید هر کاراکتری که دفعه دوم تکرار میشه مکان تکرار شدنشو هم باید ذخیره کنین و به همین ترتیب الی آخر.
البته من دقیق منظور این جمله (حالا نمیشه با هافمن کاری کرد که علاوه بر حجم تعداد کارکترها هم کمتر بشه؟) رو نفهمیدم
واضح تر بگین

negar.rafie
شنبه 25 شهریور 1391, 15:24 عصر
ببینید اگر ما بخوایم یه صفحه متن را رمزنگاری کنیم رشته رمزشده چند صفحه میشه
حالا میخوام که کاری کنیم طول رشته رمز شده کمتر بشه

kkkaka
شنبه 25 شهریور 1391, 17:10 عصر
چیزی که بنده از الگوریتم هافمن دستگیرم شد (اگر اشتباه میکنم لطفآ راهنماییم کنید)
این الگوریتم با طول رشته کاری نمیکنه فقط حجم انتقال رو کاهش میده با این صورت که کمترین بیت رو به بیشتر کاراکتر تکرار شونده میده به عنوان مثال
اگر داشته باشیم: abcdaeafab
a= 0
f =100
c =101
e =1100
d =1101
b= 111
پس:
(111110111001011000) در این صورت 16 بیت برای انتقال این رشته نیاز هست.
در حالی که اگر قرار بود رشته abcdaeafab رو به همینصورت انتقال بدیم میشد bit8*10=800bit .
امیدوارم که درست فهمیده باشم.

FastCode
شنبه 25 شهریور 1391, 20:58 عصر
سلام دوستان
من برای رمزنگاری اطلاعات از الگوریتم AES استفاده می کنم ولی به عنوان مثال اگر حرف a را رمزنگاری کنیم رشته رمزنگاری شده به صورت زیر خواهد بود :
Z+++c3ZSdlfmzLIX8SOR+A==
که خیلی طولانی و اگر بخواهیم یک جمله را رمزنگاری کنیم رشته تولید شده بسیار طولانی است
حالا برای اینکه طول رشته را کمتر کنیم باید ان را با الگوریتم هافمن فشرده کنیم ولی من نمی تونم با الگوریتم هافمن کار کنم
حالا من کلاس الگوریتم AES را میزارم اینجا لطفا بگید بعد از رمز نگاری با الگوریتم AES چطور رشته تولید شده را فشرده کنم


سلام
این تصویر رو ببینید تا علت رو توضیح بدم
http://en.wikipedia.org/wiki/File:AES-SubBytes.svghttp://en.wikipedia.org/wiki/File:AES-SubBytes.svg http://en.wikipedia.org/wiki/File:AES-SubBytes.svg
در رمز نگاری با الگوریتم های block based(همه ی الگوریتم ها تغییریباً اینطوری هستن و دسته بندی رسمی ای نداره)(الگوریتم هایی که حالت های مثل CBC CBE EBC ... دارن)
اگر تعداد byte های ورودی از تعداد بایت های block کمتر باشه,بقیه ی block ه ورودی با یک byte مثل صفر پر میشه
برای همین برای الگوریتم فرقی نداره که در حالت ۲۵۶ بیتی شما ۱ بایت بهش بدید یا ۱۶ بایت اگر ۱۵ بایت به ورودیتون اضافه کنید اندازه خروجی همین میشه.

اگر تعداد کاراکترها نسبت بزرگی با هم ندارن یعنی تعداد A ها چند برابر B ها نیست استفاده از huffman سود زیادی برای شما نخواهد داشت.
در عوض اگر سری تکراری در ورودی داشته باشید مثل ABC ABC ABC ,الگوریتم های پیچیده تر مثل Deflate/Zip یا rar و یا gzip برای شما مفیدتر خواهند بود.
هر کدام از این الگوریتم ها در یک حالا بیشترین بازدهی رو داره
gzip در stream هایی که قابلیت seek ندارند performance ه خوبی داره(مثل شبکه های با buffer ه کم/احتمالاً برنامه شما)
rar نیاز به seek داره و Deflate هم تقریباً در همه شرایط کار میکنه
Deflate در .Net framework پیاده سازی شده.

negar.rafie
شنبه 25 شهریور 1391, 21:35 عصر
حالا میشه کلاس یکی از اینهایی که معرفی کردید بزارید

FastCode
شنبه 25 شهریور 1391, 21:49 عصر
Deflate
مثال ه MSDN
http://msdn.microsoft.com/en-us/library/system.io.compression.deflatestream.aspx
using System; using System.IO; using System.IO.Compression; public class Program { public static void Main() { string directoryPath = @"c:\users\public\reports"; DirectoryInfo directorySelected = new DirectoryInfo(directoryPath); foreach (FileInfo fileToCompress in directorySelected.GetFiles()) { Compress(fileToCompress); } foreach (FileInfo fileToDecompress in directorySelected.GetFiles("*.cmp")) { Decompress(fileToDecompress); } } public static void Compress(FileInfo fileToCompress) { using (FileStream originalFileStream = fileToCompress.OpenRead()) { if ((File.GetAttributes(fileToCompress.FullName) & FileAttributes.Hidden) != FileAttributes.Hidden & fileToCompress.Extension != ".cmp") { using (FileStream compressedFileStream = File.Create(fileToCompress.FullName + ".cmp")) { using (DeflateStream compressionStream = new DeflateStream(compressedFileStream, CompressionMode.Compress)) { originalFileStream.CopyTo(compressionStream); Console.WriteLine("Compressed {0} from {1} to {2} bytes.", fileToCompress.Name, fileToCompress.Length.ToString(), compressedFileStream.Length.ToString()); } } } } } public static void Decompress(FileInfo fileToDecompress) { using (FileStream originalFileStream = fileToDecompress.OpenRead()) { string currentFileName = fileToDecompress.FullName; string newFileName = currentFileName.Remove(currentFileName.Length - fileToDecompress.Extension.Length); using (FileStream decompressedFileStream = File.Create(newFileName)) { using (DeflateStream decompressionStream = new DeflateStream(originalFileStream, CompressionMode.Decompress)) { decompressionStream.CopyTo(decompressedFileStream) ; Console.WriteLine("Decompressed: {0}", fileToDecompress.Name); } } } } }
GZipStream هم در همین namespace ه.میتونید فقط اسم ها رو در کد بالا عوض کنید
http://msdn.microsoft.com/en-us/library/system.io.compression.gzipstream.aspx
using System; using System.IO; using System.IO.Compression; namespace zip { public class Program { public static void Main() { string directoryPath = @"c:\users\public\reports"; DirectoryInfo directorySelected = new DirectoryInfo(directoryPath); foreach (FileInfo fileToCompress in directorySelected.GetFiles()) { Compress(fileToCompress); } foreach (FileInfo fileToDecompress in directorySelected.GetFiles("*.gz")) { Decompress(fileToDecompress); } } public static void Compress(FileInfo fileToCompress) { using (FileStream originalFileStream = fileToCompress.OpenRead()) { if ((File.GetAttributes(fileToCompress.FullName) & FileAttributes.Hidden) != FileAttributes.Hidden & fileToCompress.Extension != ".gz") { using (FileStream compressedFileStream = File.Create(fileToCompress.FullName + ".gz")) { using (GZipStream compressionStream = new GZipStream(compressedFileStream, CompressionMode.Compress)) { originalFileStream.CopyTo(compressionStream); Console.WriteLine("Compressed {0} from {1} to {2} bytes.", fileToCompress.Name, fileToCompress.Length.ToString(), compressedFileStream.Length.ToString()); } } } } } public static void Decompress(FileInfo fileToDecompress) { using (FileStream originalFileStream = fileToDecompress.OpenRead()) { string currentFileName = fileToDecompress.FullName; string newFileName = currentFileName.Remove(currentFileName.Length - fileToDecompress.Extension.Length); using (FileStream decompressedFileStream = File.Create(newFileName)) { using (GZipStream decompressionStream = new GZipStream(originalFileStream, CompressionMode.Decompress)) { decompressionStream.CopyTo(decompressedFileStream) ; Console.WriteLine("Decompressed: {0}", fileToDecompress.Name); } } } } } }

negar.rafie
یک شنبه 26 شهریور 1391, 12:13 عصر
ولی اینها برای فشرده کردن فایل است نه کم کردن تعداد کارکتر
یکی از دوستان تو این تاپیک (http://barnamenevis.org/showthread.php?360777-%D8%B1%D8%A7%D9%87%D9%86%D9%85%D8%A7%DB%8C%DB%8C-%D8%A8%D8%B1%D8%A7%DB%8C-%D8%B1%D9%85%D8%B2-%DA%AF%D8%B2%D8%A7%D8%B1%DB%8C&p=1592463&viewfull=1#post1592463)یه سورس گذاشتن من تقربا همچین چیزی می خوام

amir11205
یک شنبه 26 شهریور 1391, 13:54 عصر
ولی اینها برای فشرده کردن فایل است نه کم کردن تعداد کارکتر
یکی از دوستان تو این تاپیک (http://barnamenevis.org/showthread.php?360777-%D8%B1%D8%A7%D9%87%D9%86%D9%85%D8%A7%DB%8C%DB%8C-%D8%A8%D8%B1%D8%A7%DB%8C-%D8%B1%D9%85%D8%B2-%DA%AF%D8%B2%D8%A7%D8%B1%DB%8C&p=1592463&viewfull=1#post1592463)یه سورس گذاشتن من تقربا همچین چیزی می خوام
سلام
خیلی ببخشید این برنامه ای که گذاشتین چه فرقی با برنامه ای که من گذاشتم می کنه؟
شما بازم هدفتون رو مشخص نکردین
این برنامه هم کار اضافه خاصی انجام نمیده و فقط میاد تعداد تکرار هر کاراکتر و کدینگ هافمن کاراکتر رو نشون میده
بازم میگم برای اینکه تکرار رو حذف کنید یک روش پیشنهادی همونی بود که بهتون عرض کردم
خوش باشین

vaheeed
یک شنبه 26 شهریور 1391, 16:45 عصر
توضیحات دوستان خیلی کامل بود و کار هافمن دقیقا همینه ولی اگه میخوایین تعداد کاراکتر ها هم کم بشه یه راه به نظرم اومد . با هافمن طبق برنامه دوستمون تبدیلش کنید. حالا هر 8 بیت رو به مبنای بیشتر از 2 -بستگی داره بخواین چقدر تعداد کاراکتر ها کم بشه - ببرید و بعد که خواستید متن اصلی رو بدست بیارید اول هر کاراکتر رو به مبنای 2 ببرید که صفر و یک های هافمن بدست بیاد و بعد طبق هافمن کد اصلی رو بدست بیارید در واقع این یه روش ترکیببی میشه هافمن برای کم کردن حجم و تغیر مبنا برای کاهش کاراکتر. اگه روش دوم رو نفهمید این توضیح رو هم اضافه کنم که : میشه گفت یه جور تغیر متغیر هست

silverfox
یک شنبه 26 شهریور 1391, 18:00 عصر
وقتی توی حافظتون فقط مبنای 2 دارید به هر مبنایی ببرید باز باید برش گردونید دیگه، نه؟همونقدر حافظه اشغال می کنه مگه هدف از کمتر کردن کاراکتر ها همین کمتر کردن فضای اشغال شده نیست؟

FastCode
سه شنبه 28 شهریور 1391, 22:24 عصر
Stream با file فرقی نداره
شما میتونید ورودی توابع رو با یک System.Stream عوض کنید.
البته یک مقدار تغییر هم میخواد که خودتون میتونید بدید