Steqanoqrafiya dedikdə insanların ağlına terrorçular, pedofillər, casuslar və ya ən yaxşı halda kriptoanarxistlər və digər elm adamları gəlir. Və həqiqətən, başqa kimə lazım ola bilər gizlətmək xarici gözlərdən bir şey? Bunun adi bir insana nə faydası ola bilər?
Belə çıxır ki, biri var. Buna görə də bu gün biz steqanoqrafiya üsullarından istifadə edərək məlumatları sıxışdıracağıq. Və sonda oxucu fayl sistemində pulsuz gigabaytların sayını artırmaq üçün hətta JPEG formatında öz qiymətli foto arxivlərindən istifadə edə biləcək.
Nə?
Oxucu xatırlayırsa, steqanoqrafiya o qədər qəribə alqoritmlərdir ki, bir məlumatın digərinin içində olduğunu gizlətməyə imkan verir. Daha sadə dildə: şəkil + fayl == təxminən eyni şəkil, lakin tam deyil (şəkillərin əvəzinə hər şey ola bilər, lakin adətən onlarda hər şey daha aydındır). İçəridə nəyinsə olub-olmadığını müəyyən etmək üçün asan bir yol olmamalıdır.
Bəs əgər birini digərindən ayırmaq mümkün deyilsə, heç bir fərq varmı? İstehlakçı nöqteyi-nəzərindən, istifadəçi riyazi dəqiqliyə (müəyyən bir bit dəsti ilə əks olunur) əhəmiyyət vermir, yalnız onun qəbul etdiyi şeylərə əhəmiyyət verir.
Məsələn, sevimli itin üç şəklinə baxaq:
Ehtiyatlı olun, JPEG!
Ölçüdəki böyük fərqə baxmayaraq, üçüncü versiyanı az adam seçəcək. Digər tərəfdən, ilk iki fotoşəkil arasındakı fərq o qədər də nəzərə çarpan deyil və onlarda olan məlumatların miqdarı (mənim fikrimcə) bərabər ola bilər.
Bu prinsipin özü artıq köhnədir və uzun illər itkili məlumatın sıxılma üsulları ilə fəal şəkildə istifadə olunur. Amma sındırmaq tikinti deyil, biz məsələnin daha təkmil tərəfi ilə maraqlanırıq. Əlavə ölçü məlumatlarını yerləşdirmək mümkündürmü? N faylın ölçüsünü artırması üçün M < N, lakin dəyişikliklər istifadəçi üçün nəzərə çarpmadı?
Əlbəttə edə bilərsən. Ancaq dərhal bir neçə rezervasiya etməyə dəyər:
- Birincisi, metod universal olmalı və əksər giriş məlumatlarında müsbət nəticə verməlidir. Yəni, orta hesabla, təsadüfi bir giriş üçün saxlanılan məlumatın həcmində faktiki azalma olmalıdır. “Orta hesabla” əksinin baş verə biləcəyini bildirir, lakin üstünlük təşkil etməməlidir.
- İkincisi, məlumat daxil edilməzdən əvvəl sıxılmış konteynerin ölçüsü oxşar şəkildə sıxılmış modifikasiyadan daha böyük olmalıdır. LSB metodundan istifadə edərək sadəcə olaraq bir dəstə bitin BMP şəkillərinə daxil edilməsi steqaqrafik sıxılma deyil, çünki bir növ DEFLATE-dən keçdikdən sonra orijinal görüntü çox güman ki, nəzərəçarpacaq dərəcədə kiçik olacaq.
- Üçüncüsü, nəticə həyata keçirilməli və klassik üsullarla artıq sıxılmış məlumatlarla müqayisə edilməlidir. Bu, onların ehtiyatındakı fərqlərin ehtimal təsirini aradan qaldıracaq və ümumi halda daha səmərəli sıxılma təmin edəcəkdir.
Harada?
Steqanoqrafiyanın istifadəsi, sıxılmış məlumatlara əlavə olaraq, onun daxil ediləcəyi konteynerlərə ehtiyac duyacağını nəzərdə tutur. Daxil edilmiş məlumatların maksimum miqdarı əsasən fərdi xüsusiyyətlərdən asılıdır, lakin onların sayı ilə miqyaslaşdırmaq daha asandır. Buna görə də, konteyner formatı ümumi olmalıdır ki, istifadəçi "sıxılma" prosesindən hər hansı bir fayda əldə etmək üçün kifayət qədər onlara sahib olsun.
Bu kontekstdə qrafika, audio və video faylları yaxşı namizəddir. Lakin, müxtəlif formatların, kodeklərin və s. müxtəlifliyinə görə, praktikada o qədər də çox olmayan variantlardan seçim qalır.
Bütün bunları nəzərə alaraq seçimim JPEG-ə düşdü.Demək olar ki, hər kəsdə var, o, həm şəxsi, həm də biznes məqsədləri üçün geniş istifadə olunur, demək olar ki, əksər şəkillər üçün de-fakto formatdır.
Bu asılıdır?
Daha sonra çox izahat olmadan yaxın və texniki diaqramlar və təsvirlər var, buna görə də maraqlananlar “Yüksək Texnologiyalar” bölməsinə keçərək onları atlaya bilərlər.
Ümumi xüsusiyyətlər
Məlumatı harasa yerləşdirmək üçün əvvəlcə harada olduğunu müəyyənləşdirməlisiniz. Fayl sistemində istənilən sayda müxtəlif fotoşəkillər ola bilər, istifadəçi onlardan yalnız bir neçəsini istifadə etmək istəyə bilər. Belə bir arzu olunan konteyner dəstini kitabxana adlandıracağıq.
İki halda formalaşır: sıxılmadan əvvəl və dekompressiyadan əvvəl. Birinci halda, siz sadəcə olaraq faylların bir sıra fayl adlarından (yaxud daha yaxşısı, onlar üçün müntəzəm ifadədən) istifadə edə bilərsiniz, lakin ikincidə daha etibarlı bir şey tələb olunur: istifadəçi onları fayl sistemi daxilində köçürə və köçürə bilər. , bununla da onların düzgün müəyyən edilməsinə mane olur. Buna görə də, bütün dəyişikliklər edildikdən sonra onların hashlərini (md5 kifayətdir) saxlamaq lazımdır.
Bu halda, bütün fayl sistemi boyunca müntəzəm bir ifadədən istifadə edərək ilkin axtarışın aparılmasının mənası yoxdur, müəyyən bir kök kataloqunu təyin etmək kifayətdir. Sıxılmış məlumatın sonrakı bərpası üçün lazım olan digər meta-məlumatlarla birlikdə həmin hashləri ehtiva edən xüsusi arxiv faylı orada saxlanılacaq.
Bütün bunlar hər hansı bir steqaqrafik məlumatın sıxılma alqoritminin hər hansı tətbiqinə eyni dərəcədə aiddir. Məlumatların sıxılması və bərpası proseslərini qablaşdırma və qablaşdırma adlandırmaq olar.
F5
İndi nə etdiyimiz və niyə etdiyimiz aydın oldu, məqsədə çatmaq üçün alqoritmi təsvir etmək qalır. JPEG faylının kodlaşdırılması prosesini xatırlayaq (Bauman Milli Kitabxanasının vikisi sayəsində):
Buna baxaraq, dərhal bir neçə şərh vermək daha yaxşıdır:
- JPEG faylının ölçüsü onu bir növ Winrar ilə sıxışdırmağa belə cəhd etmədən optimal hesab edilə bilər;
- Ən azı məqbul performans təmin etmək üçün yalnız saxlanılan məlumat (diskret kosinus çevrilməsindən, DCT-dən əldə edilən) dəyişdirilə bilər.
- İstifadəçi üçün nəzərə çarpan sənaye miqyasında məlumatları itirməmək üçün hər bir fərdi təsvirə minimum dəyişiklik etmək lazımdır;
Bütün alqoritmlər ailəsi tanış ola biləcəyiniz bu şərtlərə uyğundur . Onlardan ən təkmil olanı alqoritmdir Andreas Westfeld tərəfindən, parlaqlıq komponentinin DCT əmsalları ilə işləyir (insan gözü onun dəyişikliklərinə ən az həssasdır). Mövcud JPEG faylı ilə işləyərkən onun ümumi tərtibatı aşağıdakı kimi göstərilir:
F5 bloku matris kodlamasına əsaslanan qabaqcıl yerləşdirmə texnikasından istifadə edir. Oxucu bu barədə və alqoritmin özü haqqında yuxarıdakı linkdə daha çox öyrənə bilər, lakin biz ilk növbədə onunla maraqlanırıq ki, onun köməyi ilə eyni miqdarda məlumatı daxil edərkən daha az dəyişiklik edə bilərsiniz, istifadə olunan konteynerin ölçüsü bir o qədər böyükdür. , və Alqoritmi yerinə yetirmək üçün yalnız sadə Huffman və RLE (de)kodlaşdırma əməliyyatlarını yerinə yetirmək lazımdır.
Dəyişikliklər özləri tam əmsallara edilir və onların mütləq dəyərinin bir azaldılması ilə nəticələnir ki, bu da ümumiyyətlə məlumatların sıxılması üçün F5-dən istifadə etməyə imkan verir. Məsələ ondadır ki, JPEG-də dəyərlərin statistik paylanması səbəbindən mütləq dəyərdə azaldılmış əmsal Huffman kodlaşdırmasından sonra çox güman ki, daha az bit tutacaq.
Sıfırın (azalma adlanan) meydana gəlməsi halında, saxlanılan məlumatların sayı ölçüsü ilə azalacaq, çünki əvvəlki müstəqil əmsal RLE kodlaşdırılmış sıfır ardıcıllığının bir hissəsi olacaqdır:
Modifikasiyalar
Məlumatların qorunması və sıxılması ortoqonal problemlərdir, ona görə də orijinal alqoritmdən gizli parol dəyişikliyinə laqeyd yanaşmaq olar. Üstəlik, məlumatların necə çıxarılmasını dəqiq bilməliyik, buna görə də bunun üçün lazım olan bütün məlumatlar (hansı konteynerlərdən istifadə edilmişdir, hansı ardıcıllıqla və s.) ayrıca faylda qeyd edilməli və arxivçi tərəfindən pulsuz oxunması üçün açıq olmalıdır.
Orijinal alqoritm məxfi mesajların ötürülməsi üçün nəzərdə tutulmuşdur, ona görə də istifadəçinin özünün zəruri hallarda, əgər varsa, onu hissələrə böləcəyini fərz edərək, bir anda yalnız bir konteynerlə işləyir. Üstəlik, hər bir konteynerə müstəqil şəkildə daxil edildikdə, hər birinə neçə bit məlumat qoymaq lazım olduğunu əvvəlcədən bilməlisiniz. Buna görə də kitabxananın hər bir elementinin əmsalları bir mücərrəd böyük birinə birləşdirilməli və orijinal alqoritmə uyğun olaraq onunla işlənməlidir.
Orijinal F5 konteyner ölçüsünün 12% -ə qədər imkan verdiyi üçün, bu modifikasiya həm də maksimum tutumu artıracaq: bütün kitabxananın ölçüsünün "12% -ə qədəri" "12% -ə qədər" cəmindən böyük və ya ona bərabərdir. "onun hər bir elementindən.
Kodlaşdırılmış ümumi sxem aşağıdakı kimidir:
Alqoritmin özü
İndi oxucunu qaranlıqda saxlamamaq üçün alqoritmin özünü başdan sona təsvir etməyin vaxtıdır:
- İstifadəçi ikili sıxıla bilən verilənləri M və L kitabxanasını müntəzəm ifadə və axtarışın kök kataloqundan istifadə edərək müəyyən edir;
- Kitabxana elementləri FS-də göründükləri ardıcıllıqla MC-ni təşkil edir:
- Fayl məlumatlarından bir sıra C əmsalları deşifr edilir;
- MC <- MC | C;
- K parametri dəhşətli bərabərsizlik əsasında müəyyən edilir:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Növbəti çəkildi
n = (1 << k) - 1MC-dən sıfır olmayan elementlərin ən az əhəmiyyətli bitləri və ona yazılıra:- Sehrli hash funksiyası nəzərə alınır
f, n-bit sözünü təmsil edirak-bits; - Əgər
s == 0, onda heç nəyi dəyişməyə ehtiyac yoxdur və alqoritm növbəti əmsallara keçir; - Məsul olan əmsalın mütləq dəyərini azaldın
s-hey sözdə bir aza; - Əgər azalma nəticəsində azalma baş verərsə (əmsal 0 olur), onda addımı əvvəldən təkrarlayın;
- Sehrli hash funksiyası nəzərə alınır
- Bütün əmsallar mənbə fayllarına yazılmış RLE və Huffman tərəfindən kodlanır;
- k parametri arxiv faylına yazılır;
- Hər bir L faylından MD5 hashı orijinal yerləşdiyi sıra ilə hesablanır və arxiv faylına yazılır.
Yüksək texnologiya
Alqoritmin sadəlövh forması və digər yüksək səviyyəli (xüsusilə zibil toplama ilə) dillərdə tətbiqlər dəhşətli performans verəcəkdir, buna görə də bütün bu mürəkkəblikləri təmiz C-də həyata keçirdim və həm icra sürəti, həm də bir sıra optimallaşdırmalar həyata keçirdim. yaddaş (siz DCT-dən əvvəl də bu şəkillərin sıxılmadan nə qədər çəkdiyini bilmirsiniz). Ancaq buna baxmayaraq, əvvəlcə icra sürəti arzuolunan bir şey buraxdı, buna görə də bütün prosesi və istifadə olunan üsulları təsvir etməyəcəyəm.
Çarpaz platforma libjpeg, pcre və tinydir kitabxanalarının birləşməsindən istifadə etməklə əldə edilir, buna görə onlara təşəkkür edirik. Varsayılan olaraq, hər şey normal vasitəsilə tərtib edilir make, buna görə də Windows istifadəçiləri özləri üçün bəzi Cygwin quraşdırmaq və ya Visual Studio və kitabxanalarla özləri məşğul olmaq istəyirlər.
Tətbiq konsol yardım proqramı və kitabxana şəklində mövcuddur. Maraqlananlar sonuncunun istifadəsi haqqında daha çox məlumatı yazının sonunda əlavə edəcəyim linki Github-dakı repozitoriyada oxuya bilərlər. Və burada işin təsvirinə və nümayişinə keçirik.
Necə istifadə etmək olar?
Diqqətlə. İstifadə olunmuş şəkillər istədiyiniz kimi köçürülə, adını dəyişdirə və kopyalana bilər. Bununla belə, son dərəcə diqqətli olmalı və onların məzmununu heç bir şəkildə dəyişdirməməlisiniz. Bir bitin dəyişdirilməsi hashı pozacaq və məlumatı bərpa etməyi qeyri-mümkün edəcək.
Tutaq ki, kompilyasiyadan sonra icra olunan f5ar faylını alırıq. Kitabxananın ölçüsünü təhlil edərək, bayraqdan istifadə edərək onun istifadə imkanlarını hesablaya bilərsiniz -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Qablaşdırma komanda tərəfindən həyata keçirilir ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], və istifadə edərək qabdan çıxarın ./f5ar -u [файл архива] [имя восстановленного файла].
Əməyin nümayişi
Metodun effektivliyini göstərmək üçün xidmətdən itlərin 225 tamamilə pulsuz foto kolleksiyasını yüklədim. . Onların hər biri adi istifadəçi fotoşəkillərindən bir qədər yüksək keyfiyyətə malikdir, amma yenə də. Kitabxananın kodlaşdırma xüsusiyyətlərinin ümumi ölçüyə təsirini neytrallaşdırmaq üçün onların hər biri libjpeg istifadə edərək yenidən kodlaşdırılıb. Sıxıla bilən məlumatların ən pis nümunəsini göstərmək üçün dd istifadə edərək təsadüfi 36 metrlik (ümumi ölçüsün 5%-dən bir qədər çoxu) vahid paylanmış fayl yaradıldı.
Test prosesi olduqca sadədir:
$ 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/Və ya pərəstişkarları üçün ekran görüntüsü
Gördüyünüz kimi, sabit diskdəki orijinal 633 + 36 == 669 meqabayt məlumatdan daha yaxşı bir 563 əldə etdik və bizə ~ 1,188 sıxılma nisbəti verdik. Bu radikal fərq klassik üsullardan (məsələn, tinyjpg) istifadə edərək JPEG fayllarının optimallaşdırılması zamanı əldə edilənlərə bənzər son dərəcə kiçik itkilərlə izah olunur. Təbii ki, steqaqrafik sıxılmadan istifadə edərkən məlumat sadəcə “itirilmir”, digər məlumatların kodlaşdırılması üçün istifadə olunur.Bundan başqa, F5-in istifadəsi ilə əlaqədar “optimallaşdırılmış” əmsalların sayı ənənəvi optimallaşdırma ilə müqayisədə xeyli azdır.
Hansı modifikasiyalar olsa da, onlar tamamilə gözə görünməzdir. Aşağıdakı spoylerin altında oxucu həm gözlə, həm də dəyişdirilmiş komponentin dəyərlərini orijinaldan çıxarmaqla fərqi qiymətləndirə bilər (rəng nə qədər səssiz olarsa, fərq o qədər kiçik olar):
Habrastorage-ə uyğun gəlməyən şəkillərə keçidlər
Orijinal -
Dəyişdirilmiş -
Fərq -
Bunun əvəzinə bir nəticəyə
Ümid edirəm ki, oxucunu belə üsulların mümkün olduğuna və yaşamaq hüququna malik olduğuna inandıra bildim. Bununla belə, sərt disk və ya əlavə kanal (şəbəkə ötürülməsi üçün) almaq bu yolla pula qənaət etməyə çalışmaqdan daha sadə seçim kimi görünə bilər. Bir tərəfdən, bu doğrudur, geniş inkişaf çox vaxt daha sadə və etibarlıdır. Amma digər tərəfdən, gərginliyi də unutmaq olmaz. Axı, sabah mağazaya gəlib özünüzə daha min terabaytlıq sərt disk ala biləcəyinizə heç bir zəmanət yoxdur, ancaq evdə artıq uzanmış disklərdən həmişə istifadə edə bilərsiniz.
->
Mənbə: www.habr.com