스테가노그래피를 사용하여 하드 드라이브 공간 절약

스테가노그래피에 대해 이야기할 때 사람들은 테러리스트, 소아성애자, 스파이, 기껏해야 암호 무정부주의자 및 기타 과학자를 떠올립니다. 그리고 실제로 누가 필요할까요? 숨다 외부 눈에서 뭔가? 이것이 보통 사람에게 무슨 유익이 있겠습니까?

하나가 있다는 것이 밝혀졌습니다. 이것이 오늘 우리가 스테가노그래피 방법을 사용하여 데이터를 압축하는 이유입니다. 그리고 결국 독자는 JPEG 형식의 소중한 사진 아카이브를 사용하여 파일 시스템의 무료 기가바이트 수를 늘릴 수도 있습니다.

뭐라구?

독자가 기억한다면, 스테가노그래피는 한 정보의 존재를 다른 정보 안에 숨길 수 있게 해주는 이상한 알고리즘입니다. 더 간단한 언어로: 그림 + 파일 == 거의 동일한 그림이지만 완전히 같지는 않습니다(그림 대신에 무엇이든 있을 수 있지만 일반적으로 모든 것이 더 명확합니다). 안에 뭔가가 있는지 없는지 쉽게 판단할 수 있는 방법이 있어서는 안 됩니다.

그러나 하나를 다른 하나와 구별할 수 없다면 전혀 차이가 있습니까? 소비자의 관점에서 볼 때, 사용자는 수학적 정밀도(특정 비트 세트에 의해 반영됨)에는 관심이 없고 단지 자신이 인식하는 것에만 관심이 있습니다.

예를 들어, 귀여운 강아지의 세 가지 이미지를 살펴보겠습니다.

조심하세요, JPEG!

크기의 큰 차이에도 불구하고 세 번째 버전을 선택하는 사람은 거의 없습니다. 반면에 처음 두 사진의 차이는 그다지 눈에 띄지 않으며 (내 관점에서 볼 때) 그 안에 담긴 정보의 양은 동일할 수 있습니다.

이 원리 자체는 이미 오래되었으며 수년 동안 손실 정보 압축 방법에 의해 적극적으로 활용되어 왔습니다. 그러나 파괴는 구축이 아니며, 우리는 이 문제의 보다 진보된 측면에 관심이 있습니다. 추가 사이즈 정보를 삽입할 수 있나요? N 크기가 증가하도록 파일에 추가 M < N, 그러나 변경 사항이 사용자에게 눈에 띄지 않았습니까?

물론 당신은 할 수. 하지만 즉시 몇 가지 예약을 할 가치가 있습니다.

• 첫째, 방법은 보편적이어야 하며 대부분의 입력 데이터에 대해 긍정적인 결과를 제공해야 합니다. 즉, 평균적으로 무작위 입력의 경우 저장된 정보의 양이 실제로 감소해야 합니다. "평균적으로"는 반대가 발생할 수 있지만 우세해서는 안 된다는 의미입니다.
• 둘째, 정보를 삽입하기 전 압축된 컨테이너의 크기는 유사한 방식으로 압축된 수정본보다 커야 합니다. 단순히 LSB 방법을 사용하여 BMP 이미지에 여러 비트를 삽입하는 것은 스테가노그래픽 압축이 아닙니다. 일종의 DEFLATE를 실행하면 원본 이미지가 눈에 띄게 작아질 가능성이 높기 때문입니다.
• 셋째, 기존 방법으로 이미 압축된 데이터에 대해 결과를 수행하고 비교해야 합니다. 이렇게 하면 중복성 차이로 인한 확률적 효과가 제거되고 일반적인 경우에 보다 효율적인 압축이 제공됩니다.

어디서?

스테가노그래피를 사용한다는 것은 압축된 정보 외에도 해당 정보를 내장할 컨테이너가 필요하다는 것을 의미합니다. 포함된 정보의 최대량은 주로 개별 속성에 따라 다르지만 해당 수에 따라 확장하는 것이 훨씬 쉽습니다. 따라서 사용자가 "압축" 프로세스에서 이점을 얻을 수 있도록 컨테이너 형식은 공통되어야 합니다.

이러한 맥락에서 그래픽, 오디오 및 비디오 파일이 좋은 후보입니다. 그러나 다양한 형식, 코덱 등으로 인해 실제로는 그렇게 많지 않은 옵션 중에서 선택할 수 있습니다.

이 모든 것을 고려하여 제가 선택한 JPEG는 거의 모든 사람이 가지고 있으며 개인 및 비즈니스 목적으로 널리 사용되며 대부분의 이미지에 대한 사실상의 형식입니다.

때에 따라 다르지?

그 다음에는 별다른 설명 없이 대략적이고 기술적인 다이어그램과 설명이 있으므로 관심이 있는 사람은 "첨단 기술" 섹션으로 스크롤하여 해당 내용을 건너뛸 수 있습니다.

공통 기능

데이터를 어딘가에 삽입하려면 먼저 위치를 결정해야 합니다. 파일 시스템에는 다양한 사진이 얼마든지 있을 수 있으며, 사용자는 그중 몇 장만 사용하기를 원할 수 있습니다. 우리는 그러한 원하는 컨테이너 세트를 라이브러리라고 부를 것입니다.

압축 전과 압축 해제 전의 두 가지 경우로 구성됩니다. 첫 번째 경우에는 단순히 파일 이름 집합(또는 정규식을 사용하는 것이 더 좋음)을 사용할 수 있지만 두 번째 경우에는 보다 안정적인 것이 필요합니다. 즉, 사용자가 파일 시스템 내에서 해당 파일을 복사하고 이동할 수 있습니다. , 이로 인해 올바르게 식별되지 않습니다. 따라서 모든 수정이 완료된 후에는 해시(md5이면 충분함)를 저장해야 합니다.

이 경우 전체 파일 시스템에서 정규식을 사용하여 초기 검색을 수행하는 것은 의미가 없으며 특정 루트 디렉터리를 지정하는 것으로 충분합니다. 압축된 정보의 후속 복구에 필요한 기타 메타정보와 함께 해당 해시를 포함하는 특수 아카이브 파일이 여기에 저장됩니다.

이 모든 것은 스테가노그래피 데이터 압축 알고리즘의 모든 구현에 동일하게 적용됩니다. 데이터 압축 및 복구 프로세스 자체를 압축 및 압축 풀기라고 할 수 있습니다.

F5

이제 우리가 무엇을, 왜 하는지 명확해졌으므로 목표 달성을 위한 알고리즘을 설명하는 일만 남았습니다. JPEG 파일을 인코딩하는 과정을 떠올려 보겠습니다(Bauman National Library의 위키 덕분에):

이를 살펴보면 즉시 몇 가지 의견을 제시하는 것이 좋습니다.

• JPEG 파일의 크기는 일종의 Winrar로 압축하지 않고도 최적의 크기로 간주될 수 있습니다.
• 저장된 정보(이산 코사인 변환, DCT의 출력)만 수정하여 최소한 허용 가능한 성능을 제공할 수 있습니다.
• 사용자가 눈에 띄는 산업 규모의 데이터를 잃지 않으려면 각 개별 이미지를 최소한으로 수정해야 합니다.

전체 알고리즘 제품군이 이러한 조건에 적합하며 이에 익숙해질 수 있습니다. 이 좋은 발표에. 그 중 가장 발전된 것은 알고리즘이다. F5 Andreas Westfeld가 밝기 구성 요소의 DCT 계수를 사용하여 작업합니다(사람의 눈은 변화에 가장 민감하지 않습니다). 기존 JPEG 파일로 작업할 때의 일반적인 레이아웃은 다음과 같이 표시됩니다.

F5 블록은 매트릭스 인코딩을 기반으로 한 고급 임베딩 기술을 사용합니다. 독자는 위 링크에서 이 알고리즘과 알고리즘 자체에 대해 자세히 알아볼 수 있지만, 우리는 이 도움을 통해 동일한 양의 정보를 삽입할 때 더 적은 변경 사항을 적용할 수 있고 사용되는 컨테이너의 크기가 더 커진다는 사실에 주로 관심이 있습니다. , 그리고 알고리즘을 수행하기 위해서는 간단한 허프만 및 RLE (디)코딩 작업만 수행하면 됩니다.

변경 자체는 정수 계수에 적용되며 절대값을 5씩 줄여서 일반적으로 데이터 압축에 FXNUMX를 사용할 수 있습니다. 요점은 JPEG 값의 통계적 분포로 인해 절대값으로 감소된 계수가 허프만 인코딩 후 더 적은 비트를 차지할 가능성이 높다는 것입니다.

XNUMX이 형성되는 경우(소위 축소) 이전의 독립 계수가 RLE로 인코딩된 XNUMX 시퀀스의 일부가 되므로 저장된 정보의 수가 크기에 따라 줄어듭니다.

수정

데이터 보호와 압축은 직교 문제이므로 원래 알고리즘의 비밀 비밀번호 순열은 무시할 수 있습니다. 또한 데이터를 추출하는 방법을 정확히 알아야 하므로 이에 필요한 모든 정보(사용된 컨테이너, 사용된 순서 등)는 별도의 파일에 기록하고 아카이버가 무료로 읽을 수 있도록 공개해야 합니다.

원래 알고리즘은 비밀 메시지를 전송하도록 설계되었으므로 사용자가 필요할 경우 컨테이너를 여러 부분으로 나눌 것이라는 가정 하에 한 번에 하나의 컨테이너에서만 작동합니다. 또한 각 컨테이너에 독립적으로 포함되는 경우 각 컨테이너에 몇 비트의 데이터를 넣을지 미리 알아야 합니다. 따라서 라이브러리의 각 요소의 계수는 하나의 추상적이고 큰 요소로 결합되어 원래 알고리즘에 따라 작업되어야 합니다.

원래 F5는 컨테이너 크기의 최대 12%를 허용하므로 이 수정으로 최대 용량도 증가합니다. 전체 라이브러리 크기의 "최대 12%"는 "최대 12%"의 합계보다 크거나 같습니다. "를 각 요소에서 가져옵니다.

성문화된 일반 계획은 다음과 같습니다.

알고리즘 자체

이제 독자가 혼란에 빠지지 않도록 알고리즘 자체를 처음부터 끝까지 설명할 차례입니다.

• 사용자는 정규식과 검색 루트 디렉터리를 사용하여 이진 압축 데이터 M과 라이브러리 L을 정의합니다.
• FS에 나타나는 순서대로 라이브러리 요소는 MC를 구성합니다.
  • 일련의 계수 C가 파일 데이터에서 디코딩됩니다.
  • MC <- MC | 씨;
• 매개변수 k는 끔찍한 부등식을 기반으로 결정됩니다. |M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1);
• 다음 촬영 n = (1 << k) - 1 MC에서 XNUMX이 아닌 요소의 최하위 비트를 작성하고 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장의 개 사진 모음을 업로드했습니다. Unsplash. 각각은 일반 사용자 사진보다 품질이 약간 높지만 여전히 그렇습니다. 라이브러리의 인코딩 기능이 전체 크기에 미치는 영향을 중화하기 위해 각각은 libjpeg를 사용하여 다시 인코딩되었습니다. 압축 가능한 데이터의 최악의 예를 나타내기 위해 dd를 사용하여 임의의 36미터(전체 크기의 5%가 약간 넘는) 균일하게 분산된 파일을 생성했습니다.

테스트 과정은 매우 간단합니다.

$ 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 == 669MB의 데이터에서 우리는 ~563의 압축률을 제공하는 더 좋은 1,188을 얻었습니다. 이러한 근본적인 차이는 매우 작은 손실로 설명됩니다. 이는 고전적인 방법(예:tinyjpg)을 사용하여 JPEG 파일을 최적화할 때 얻은 손실과 유사합니다. 당연히 스테가노그래픽 압축을 사용하면 정보가 단순히 "손실"되는 것이 아니라 다른 데이터를 인코딩하는 데 사용됩니다. 또한 F5 사용으로 인해 "최적화된" 계수의 수가 기존 최적화보다 훨씬 적습니다.

어떤 수정이 있더라도 눈에는 전혀 보이지 않습니다. 아래 스포일러에서 독자는 눈으로 차이를 평가할 수도 있고 원본에서 변경된 구성 요소의 값을 빼서 차이를 평가할 수도 있습니다(색상이 약해질수록 차이가 작아짐).

habrastorage에 맞지 않는 이미지에 대한 링크

원래의 - https://i.ibb.co/wNDLNcZ/1.jpg
수정됨 - https://i.ibb.co/qWvpfFM/1.jpg
차이점 - https://i.ibb.co/2ZzhHfD/diff.jpg

대신 결론

그러한 방법이 가능하고 생명권이 있다는 것을 독자들에게 확신시킬 수 있었으면 좋겠습니다. 그러나 하드 드라이브나 추가 채널(네트워크 전송용)을 구입하는 것이 이러한 방식으로 비용을 절약하려는 것보다 훨씬 더 간단한 옵션처럼 보일 수 있습니다. 한편으로는 이것이 사실입니다; 광범위한 개발이 종종 더 간단하고 더 안정적입니다. 하지만 반면에 강렬함도 잊어서는 안 됩니다. 결국, 내일 상점에 와서 천 테라바이트의 하드 드라이브를 추가로 구입할 수 있다는 보장은 없지만 이미 집에 누워 있는 드라이브는 언제든지 사용할 수 있습니다.

-> GitHub의

출처: www.habr.com