عندما نتحدث عن إخفاء المعلومات، يفكر الناس في الإرهابيين، أو المتحرشين بالأطفال، أو الجواسيس، أو في أفضل الأحوال، الفوضويين السريين وغيرهم من العلماء. وحقا، من قد يحتاج آخر إخفاء شيء من عيون خارجية؟ ماذا يمكن أن تكون فائدة هذا لشخص عادي؟
اتضح أن هناك واحدا. ولهذا السبب سنقوم اليوم بضغط البيانات باستخدام أساليب إخفاء المعلومات. وفي النهاية، سيتمكن القارئ من استخدام أرشيفات الصور الثمينة بصيغة JPEG لزيادة عدد الجيجابايت المجانية في نظام الملفات.
ماذا؟
إذا كان القارئ يتذكر، فإن إخفاء المعلومات عبارة عن خوارزميات غريبة تجعل من الممكن إخفاء وجود معلومة داخل أخرى. بلغة أبسط: صورة + ملف == نفس الصورة تقريبًا، ولكن ليس تمامًا (بدلاً من الصور يمكن أن يكون هناك أي شيء، ولكن عادةً ما يكون كل شيء أكثر وضوحًا فيها). لا ينبغي أن تكون هناك طريقة سهلة لتحديد ما إذا كان هناك شيء ما بالداخل أم لا.
ولكن إذا لم يكن من الممكن تمييز أحدهما عن الآخر، فهل هناك فرق على الإطلاق؟ من وجهة نظر المستهلك، لا يهتم المستخدم بالدقة الرياضية (التي تعكسها مجموعة معينة من البتات)، بل يهتم فقط بما يدركه.
على سبيل المثال، دعونا نلقي نظرة على ثلاث صور لكلب لطيف:
احذر يا جي بي إي جي!
على الرغم من الاختلاف الكبير في الحجم، إلا أن القليل من الناس سيختارون الإصدار الثالث. من ناحية أخرى، فإن الفرق بين الصورتين الأولين ليس ملحوظًا جدًا، ويمكن أن تكون كمية المعلومات الموجودة فيهما (من وجهة نظري) متساوية.
هذا المبدأ نفسه قديم بالفعل وقد تم استغلاله بشكل نشط من خلال أساليب ضغط المعلومات المفقودة لسنوات عديدة. لكن الكسر لا يعني البناء، فنحن مهتمون بالجانب الأكثر تقدماً من القضية. هل من الممكن تضمين معلومات حجم إضافية N إلى الملف بحيث يزيد حجمه M < Nولكن التغييرات لم تكن ملحوظة للمستخدم؟
بالتأكيد تستطيع. لكن الأمر يستحق إجراء بعض التحفظات على الفور:
- أولاً، يجب أن تكون الطريقة عالمية وتعطي نتيجة إيجابية على معظم البيانات المدخلة. وهذا هو، في المتوسط، بالنسبة للإدخال العشوائي، يجب أن يكون هناك انخفاض فعلي في كمية المعلومات المخزنة. "في المتوسط" تعني أن العكس قد يحدث، ولكن لا ينبغي أن يكون هو السائد.
- ثانياً: يجب أن يكون حجم الحاوية المضغوطة قبل تضمين المعلومات أكبر من حجمها المضغوط بنفس الطريقة. إن مجرد تضمين مجموعة من البتات في صور BMP باستخدام طريقة LSB لا يعد ضغطًا مخفيًا، نظرًا لأنه بعد تشغيلها من خلال نوع من DEFLATE، فمن المرجح أن تكون الصورة الأصلية أصغر بشكل ملحوظ.
- ثالثا، يجب تنفيذ النتيجة ومقارنتها بالبيانات المضغوطة بالفعل بالطرق الكلاسيكية. سيؤدي هذا إلى إزالة التأثير الاحتمالي للاختلافات في تكرارها وتوفير ضغط أكثر كفاءة في الحالة العامة.
أين؟
إن استخدام تقنية إخفاء المعلومات يشير إلى أننا، بالإضافة إلى المعلومات المضغوطة، سنحتاج إلى حاويات سيتم تضمينها فيها. يعتمد الحد الأقصى لمقدار المعلومات المضمنة إلى حد كبير على الخصائص الفردية، ولكن من الأسهل بكثير قياسها حسب عددها. لذلك، يجب أن يكون تنسيق الحاوية شائعًا بحيث يكون لدى المستخدم ما يكفي منه ليحصل على أي فائدة من عملية "الضغط".
في هذا السياق، تعد ملفات الرسومات والصوت والفيديو مرشحة جيدة. ولكن، نظرًا لتنوع التنسيقات المختلفة وبرامج الترميز وما إلى ذلك، في الممارسة العملية، لا يتبقى لنا سوى الاختيار من بين خيارات قليلة جدًا.
وبالنظر إلى كل هذا، وقع اختياري على صيغة JPEG. وهي متوفرة لدى الجميع تقريبا، فهي تستخدم على نطاق واسع للأغراض الشخصية والتجارية، كونها التنسيق الفعلي تقريبا لأغلب الصور.
هذا يعتمد؟
بعد ذلك توجد مخططات وأوصاف قريبة وتقنية دون الكثير من الشرح، لذلك يمكن للمهتمين تخطيها عن طريق التمرير إلى قسم "التقنيات العالية".
السمات المشتركة
لتضمين البيانات في مكان ما، يجب عليك أولاً تحديد مكانها. يمكن أن يكون هناك أي عدد من الصور المختلفة في نظام الملفات، والتي قد يرغب المستخدم في استخدام عدد قليل منها فقط. سوف نسمي هذه المجموعة المرغوبة من الحاويات مكتبة.
ويتم تشكيله في حالتين: قبل الضغط وقبل فك الضغط. في الحالة الأولى، يمكنك ببساطة استخدام مجموعة من أسماء الملفات (أو الأفضل من ذلك، تعبير عادي لها) من الملفات، ولكن في الحالة الثانية، مطلوب شيء أكثر موثوقية: يمكن للمستخدم نسخها ونقلها داخل نظام الملفات ، وبالتالي منعهم من التعرف عليهم بشكل صحيح. ولذلك، فمن الضروري تخزين التجزئة الخاصة بهم (MD5 يكفي) بعد إجراء جميع التعديلات.
في هذه الحالة، ليس من المنطقي إجراء البحث الأولي باستخدام تعبير عادي في جميع أنحاء نظام الملفات بأكمله، وهو ما يكفي لتحديد دليل جذر معين. سيتم حفظ ملف أرشيف خاص فيه، والذي سيحتوي على تلك التجزئات، إلى جانب المعلومات الوصفية الأخرى اللازمة لاسترداد المعلومات المضغوطة لاحقًا.
كل هذا ينطبق بالتساوي على أي تطبيق لأي خوارزمية لضغط البيانات. يمكن أن تسمى عمليات ضغط البيانات واستعادتها نفسها بالتعبئة والتفريغ.
F5
والآن بعد أن أصبح من الواضح ما نقوم به ولماذا، يبقى وصف الخوارزمية لتحقيق الهدف. لنتذكر عملية ترميز ملف JPEG (بفضل ويكي مكتبة بومان الوطنية):
بالنظر إلى الأمر، من الأفضل تقديم بعض التعليقات على الفور:
- يمكن اعتبار حجم ملف JPEG هو الأمثل دون محاولة ضغطه باستخدام برنامج Winrar؛
- يمكن فقط تعديل المعلومات المخزنة (التي يتم إخراجها من تحويل جيب التمام المنفصل، DCT) لتوفير أداء مقبول على الأقل.
- من أجل عدم فقدان البيانات على نطاق صناعي ملحوظ للمستخدم، من الضروري إجراء الحد الأدنى من التعديلات على كل صورة على حدة؛
مجموعة كاملة من الخوارزميات تناسب هذه الشروط، والتي يمكنك التعرف عليها بنفسك . الأكثر تقدما منهم هو الخوارزمية بواسطة أندرياس ويستفيلد، يعمل باستخدام معاملات DCT لعنصر السطوع (العين البشرية هي الأقل حساسية لتغيراتها). يتم عرض تخطيطه العام عند العمل باستخدام ملف JPEG موجود كما يلي:
تستخدم الكتلة F5 تقنية تضمين متقدمة تعتمد على تشفير المصفوفة. يمكن للقارئ معرفة المزيد عنها وعن الخوارزمية نفسها على الرابط أعلاه، لكننا مهتمون في المقام الأول بحقيقة أنه بمساعدتها يمكنك إجراء تغييرات أقل عند تضمين نفس الكمية من المعلومات، كلما زاد حجم الحاوية المستخدمة ولتنفيذ الخوارزمية تحتاج فقط إلى إجراء عمليات ترميز Huffman و RLE البسيطة.
يتم إجراء التغييرات نفسها على معاملات الأعداد الصحيحة وتؤدي إلى تقليل قيمتها المطلقة بمقدار واحد، مما يسمح، بشكل عام، باستخدام F5 لضغط البيانات. والحقيقة هي أن المعامل المنخفض في القيمة المطلقة سيشغل على الأرجح عددًا أقل من البتات بعد تشفير هوفمان بسبب التوزيع الإحصائي للقيم في JPEG.
في حالة تكوين صفر (ما يسمى بالتخفيض)، سيتم تقليل عدد المعلومات المخزنة حسب حجمها، حيث سيصبح المعامل المستقل السابق جزءًا من تسلسل الأصفار المشفر RLE:
التعديلات
تعتبر حماية البيانات وضغطها من المشاكل المتعامدة، لذا يمكن إهمال تبديل كلمة المرور السرية من الخوارزمية الأصلية. علاوة على ذلك، نحتاج إلى معرفة كيفية استخراج البيانات بالضبط، لذلك يجب تسجيل جميع المعلومات اللازمة لذلك (أي الحاويات تم استخدامها، وبأي ترتيب، وما إلى ذلك) في ملف منفصل وأن تكون مفتوحة للقراءة المجانية بواسطة الأرشيف.
تم تصميم الخوارزمية الأصلية لنقل الرسائل السرية، لذا فهي تعمل مع حاوية واحدة فقط في كل مرة، على افتراض أن المستخدم نفسه سوف يقوم بتقسيمها إلى أجزاء إذا لزم الأمر، إن وجدت. علاوة على ذلك، عند تضمينها بشكل مستقل في كل حاوية، ستحتاج إلى معرفة عدد وحدات بت البيانات التي يجب وضعها في كل حاوية مسبقًا. لذلك يجب دمج معاملات كل عنصر من عناصر المكتبة في ملخص واحد كبير والعمل معه وفقًا للخوارزمية الأصلية.
نظرًا لأن F5 الأصلي يسمح بما يصل إلى 12% من حجم الحاوية، فإن هذا التعديل سيزيد أيضًا من السعة القصوى: "ما يصل إلى 12%" من حجم المكتبة بأكملها أكبر من أو يساوي مجموع "ما يصل إلى 12%" "من كل عنصر من عناصره.
المخطط العام المقنن هو كما يلي:
الخوارزمية نفسها
حان الوقت الآن لوصف الخوارزمية نفسها من البداية إلى النهاية، حتى لا نبقي القارئ في الظلام:
- يحدد المستخدم البيانات الثنائية القابلة للضغط M والمكتبة L باستخدام تعبير عادي ودليل جذر البحث؛
- بالترتيب الذي تظهر به على FS، تشكل عناصر المكتبة MC:
- يتم فك تشفير سلسلة من المعاملات C من بيانات الملف؛
- مولودية <- مولودية | ج؛
- يتم تحديد المعلمة k بناءً على عدم المساواة الرهيبة:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - اتخذت المقبل
n = (1 << k) - 1البتات الأقل أهمية من العناصر غير الصفرية من MC ومكتوبة إليهاa:- تعتبر وظيفة التجزئة السحرية
f، تمثل كلمة n بتaإلى k بتs; - إذا
s == 0، فليست هناك حاجة لتغيير أي شيء وتنتقل الخوارزمية إلى المعاملات التالية؛ - تقليل القيمة المطلقة للمعامل المسؤول عن
s-يا قليلا في الكلمةa; - إذا حدث تخفيض نتيجة التخفيض (يصبح المعامل 0)، كرر الخطوة من البداية؛
- تعتبر وظيفة التجزئة السحرية
- يتم ترميز جميع المعاملات بواسطة RLE وHuffman، ويتم كتابتها في الملفات المصدر؛
- تتم كتابة المعلمة k في ملف الأرشيف؛
- يتم حساب تجزئة MD5 من كل ملف L بترتيب موقعه الأصلي وكتابته في ملف الأرشيف.
التكنولوجيا العالية
إن الشكل الساذج للخوارزمية والتطبيقات في اللغات الأخرى عالية المستوى (خاصة مع جمع البيانات المهملة) من شأنه أن يعطي أداءً سيئًا، لذلك قمت بتنفيذ كل هذه التعقيدات في لغة C النقية وقمت بتنفيذ عدد من التحسينات من حيث سرعة التنفيذ و الذاكرة (ليس لديك أي فكرة عن مقدار وزن هذه الصور بدون ضغط حتى قبل DCT). ولكن على الرغم من ذلك، في البداية، تركت سرعة التنفيذ الكثير مما هو مرغوب فيه، لذلك لن أصف العملية بأكملها والأساليب المستخدمة.
يتم تحقيق النظام الأساسي المشترك باستخدام مجموعة من مكتبات libjpeg وpcre وtinydir، والتي نشكرهم عليها. بشكل افتراضي، يتم تجميع كل شيء عبر العادي make، لذلك يرغب مستخدمو Windows في تثبيت بعض Cygwin لأنفسهم، أو التعامل مع Visual Studio والمكتبات بأنفسهم.
التنفيذ متاح في شكل أداة مساعدة ومكتبة لوحدة التحكم. يمكن للمهتمين معرفة المزيد حول استخدام هذا الأخير في الملف التمهيدي في المستودع على Github، الرابط الذي سأرفقه في نهاية المنشور. وهنا ننتقل إلى وصف وتوضيح العمل.
كيف تستعمل؟
بحرص. يمكن نقل الصور المستخدمة وإعادة تسميتها ونسخها حسب الرغبة. ومع ذلك، يجب عليك توخي الحذر الشديد وعدم تغيير محتوياتها بأي شكل من الأشكال. سيؤدي تغيير بت واحد إلى تعطيل التجزئة ويجعل من المستحيل استعادة المعلومات.
لنفترض أنه بعد التجميع حصلنا على الملف القابل للتنفيذ f5ar. يمكنك تحليل حجم المكتبة لحساب إمكانيات استخدامها باستخدام العلم -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. التعبئة والتغليف تتم من قبل الفريق ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива]، والتفريغ باستخدام ./f5ar -u [файл архива] [имя восстановленного файла].
مظاهرة العمل
ولإظهار فعالية الطريقة، قمت بتحميل مجموعة من 225 صورة مجانية تمامًا للكلاب من الخدمة . كل واحد منهم لديه جودة أعلى قليلا من صور المستخدم العادية، ولكن لا يزال. تمت إعادة تشفير كل منها باستخدام libjpeg لتحييد تأثير ميزات تشفير المكتبة على الحجم الإجمالي. للإشارة إلى أسوأ مثال للبيانات القابلة للضغط، تم إنشاء ملف عشوائي بطول 36 مترًا (أكثر بقليل من 5% من الحجم الإجمالي) موزعًا بشكل موحد باستخدام dd.
عملية الاختبار بسيطة للغاية:
$ ls
binary_data dogs f5ar
$ du -sh dogs/
633M dogs/
$ du -h binary_data
36M binary_data
$ ./f5ar -p dogs/ .*jpg binary_data dogs.f5ar
Reading compressing file... ok
Initializing the archive... ok
Analysing library capacity... done in 16.8s
Detected somewhat guaranteed capacity of 48439359 bytes
Detected possible capacity of upto 102618787 bytes
Compressing... done in 32.6s
Saving the archive... ok
$ ./f5ar -u dogs/dogs.f5ar unpacked
Initializing the archive... ok
Reading the archive file... ok
Filling the archive with files... done in 1.2s
Decompressing... done in 17.5s
Writing extracted data... ok
$ sha1sum binary_data unpacked
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 unpacked
$ du -sh dogs/
563M dogs/أو لقطة شاشة للجماهير
كما ترون، من 633 + 36 == 669 ميجابايت من البيانات الأصلية الموجودة على القرص الصلب، انتهى بنا الأمر إلى 563 أفضل، مما يمنحنا نسبة ضغط تصل إلى 1,188 تقريبًا. يتم تفسير هذا الاختلاف الجذري من خلال خسائر صغيرة للغاية، مماثلة لتلك التي يتم الحصول عليها عند تحسين ملفات JPEG باستخدام الطرق الكلاسيكية (مثل tinyjpg). وبطبيعة الحال، عند استخدام ضغط إخفاء المعلومات، لا يتم "فقدان" المعلومات فحسب، بل يتم استخدامها لتشفير بيانات أخرى. علاوة على ذلك، فإن عدد المعاملات "المحسنة" بسبب استخدام F5 أقل بكثير من التحسين التقليدي.
ومهما كانت التعديلات الموجودة، فهي غير مرئية تمامًا للعين. تحت المفسد أدناه، يمكن للقارئ تقييم الفرق بالعين المجردة وبطرح قيم المكون المتغير من الأصل (كلما كان اللون أكثر كتمًا، كان الفرق أصغر):
روابط للصور التي لا تتناسب مع habrastorage
إبداعي -
معدل -
اختلاف -
بدلا من خاتمة
أتمنى أن أكون قد تمكنت من إقناع القارئ بأن مثل هذه الأساليب ممكنة ولها الحق في الحياة. ومع ذلك، قد يبدو شراء قرص صلب أو قناة إضافية (للنقل عبر الشبكة) خيارًا أبسط بكثير من محاولة توفير المال بهذه الطريقة. من ناحية، هذا صحيح؛ التطوير الشامل غالبًا ما يكون أبسط وأكثر موثوقية. ولكن من ناحية أخرى، لا ينبغي لنا أن ننسى المكثفة. بعد كل شيء، ليس هناك ما يضمن أنك ستتمكن غدًا من القدوم إلى المتجر وشراء محرك أقراص ثابت آخر بسعة ألف تيرابايت لنفسك، ولكن يمكنك دائمًا استخدام تلك الموجودة لديك بالفعل في المنزل.
->
المصدر: www.habr.com