希尔伯特曲线

专题

发布日期: 2024-12-12

认识希尔伯特曲线

希尔伯特曲线是一种曲线，只要恰当选择函数，画出一条连续的参数曲线，当参数t在0，1区间取值时，曲线将遍历单位正方形中所有的点，得到一条充满空间的曲线。 希尔伯特曲线是一条连续而又不可导的曲线。

可以看看这个视频

希尔伯特曲线：无限数学怎样应用于有限世界（中英字幕）_哔哩哔哩_bilibili

一种降维打击的可视化方案_哔哩哔哩_bilibili

简介

1
2
3

1890年，意大利数学家皮亚诺（Peano G）提出能填满一个正方形的曲线，叫做皮亚诺曲线。后来，由希尔伯特作出了这条曲线，又名希尔伯特曲线。皮亚诺对区间[0，1]上的点和正方形上的点的对应作了详细的数学描述。实际上，正方形的这些点对于t∈[0,1],可规定两个连续函数x=f（t）和y=g（t），使得x和y取属于单位正方形的每一个值。 [1]
希尔伯特曲线是一种能填充满一个平面正方形的分形曲线（空间填充曲线），由大卫·希尔伯特在1891年提出。
由于它能填满平面，它的豪斯多夫维是2。取它填充的正方形的边长为1，第n步的希尔伯特曲线的长度是2n - 2-n。

L系统记法：
变数: L, R
常数: F, +, -
公理: L
规则:
L → + R F - L F L - F R +
R → − L F + R F R + F L −
F ： 向前
- ： 右转90°
+ ： 左转90°
一般来说，一维的东西是不可能填满2维的方格的。但是皮亚诺曲线恰恰给出了反例。这说明我们对维数的认识是有缺陷的，有必要重新考察维数的定义。这就是分形几何考虑的问题。在分形几何中， 维数可以是分数叫做分维

Hilbert曲线的性质

升阶

已经生成了上一阶 希尔伯特曲线 后生成下一阶，需要：

把之前每个子正方形继续四等分，每4个小的正方形先生成上一阶阶希尔伯特曲线；
每个小的四等分中第三第四象限的曲线分别沿两个对角线翻转；
添加三条线段把 4 个上一阶的希尔伯特曲线首尾相连。

编码映射

在希尔伯特曲线的构造过程中，可以对每个小正方形进行二进制编码。这样，正方形中的每个点都可以与一个[0,1]区间内的编码相对应，实现了从平面到一维区间的映射

构造

取一个正方形，并将其分成9个相等的小正方形。
从左下角的正方形开始至右上角的正方形结束，依次把小正方形的中心用线段连接起来。
接下来，把每个小正方形再分成9个更小的正方形，并重复上述连接中心点的过程。
将这种操作手续无限进行下去，最终得到的极限情况的曲线就是希尔伯特曲线。

算法

public class Hilbert{
	final int SIZE=400;
	private int rank=1;
	boolean[][]  data=new boolean[SIZE][SIZE];
	public void h1() {	
		for(int i=(int) (0.25*SIZE)-1;i<(int) (0.75*SIZE);i++) {
			data[(int)(0.25*SIZE)][i]=true;
		}
		for(int j=(int) (0.25*SIZE)-1;j<(int) (0.75*SIZE);j++) {
			data[j][(int) (0.75*SIZE)]=true;
		}
		for(int i=(int) (0.25*SIZE)-1;i<(int) (0.75*SIZE);i++) {
			data[(int) (0.75*SIZE)][i]=true;
		}
	}
	public void line(int a,int b,int c, int d) {
		for(int i=a;i<=c;i++) {
			for(int j=b;j<=d;j++) {		
				data[i][j]=true;
			}
		}
	}
	public boolean[][] narrow() {
		boolean[][]  array=new boolean[SIZE/2][SIZE/2];
		for(int i=0;i<SIZE-1;i+=2) {
			for(int j=0;j<SIZE-1;j+=2) {
				if(data[i][j]||data[i][j+1]||data[i+1][j]||data[i+1][j+1]) {
					array[i/2][j/2]=true;
				}
			}
		}
		return array;
	}
	public void grow() {
		boolean[][]  nar = narrow();
		for(int i=0;i<SIZE/2;i++) {
			for(int j=0;j<SIZE/2;j++) {		
				data[i][j+SIZE/2]= nar[i][j];
			}
		}
		//旋转放置于左上角
		boolean[][] tran = transposition( nar,false);
		for(int i=0;i<SIZE/2;i++) {
			for(int j=0;j<SIZE/2;j++) {		
				data[i][j]=tran[i][j];
			}
		}
		//左右镜像对称
		for(int i=0;i<SIZE/2;i++) {
			for(int j=0;j<SIZE;j++) {		
				data[SIZE-i-1][j]=data[i][j];
			}
		}
		++rank;
		int n=(int)( Math.pow(2,rank-1))-1;
		int eg=(int)( Math.pow(0.5,rank)*SIZE);
		int bd=eg/2;
		line(bd,bd+n*eg,bd,bd+n*eg+eg);
		line(bd+n*eg,bd+n*eg+eg,bd+n*eg+eg,bd+n*eg+eg);
		line(bd+2*n*eg+eg,bd+n*eg,bd+2*n*eg+eg,bd+n*eg+eg);
	}
	//key为true时关于右倾对角线对称
	//key为false时关于左倾对角线对称
	public boolean[][] transposition(boolean[][] array,boolean key){
		int size=array.length;
		boolean[][] tran = new boolean[size][size];
		for(int i=0;i<size;i++) {
			for(int j=0;j<size;j++) {
				if(key) {
					tran[i][j]=array[j][size-1-i];
				}else{
					tran[i][j]=array[j][i];
				}
			}
		}
		return tran;
	}
}

ctf例题

题型一:图片文件

JPGDiff

下载附件

hint.png

ct.png

hint.png提示是希伯尔特曲线，ct.png发现什么都不显示，查看属性

1*65536的图片

exp1:

import PIL.Image 
from hilbertcurve.hilbertcurve import HilbertCurve 
p,n = 256,2 
ct = PIL.Image.open(r'E:\\希尔伯特\\ct.png').convert('RGB') 
print(ct.width,ct.height)
pt = PIL.Image.new('RGB',(p,p))
print('step2')
hilbert_curve = HilbertCurve(p,n) 
distances = list(range(p**2)) 
points = hilbert_curve.points_from_distances(distances) 
print('step3') 
for point, dist in zip(points, distances): 
 x,y = point 
 print(x,y)
 pix = ct.getpixel((0,dist)) 
 pt.putpixel((x,y),pix) 
pt.save(r'E:\\希尔伯特\\flag.png')

运行得到

题型二：excel表格

你这flag保熟吗

下载附件

解压rar压缩包发现有密码，尝试foremost分离两个图片

excel查看password.xls

查看hint.txt

尝试按hint字符顺序连接

希伯尔特曲线

使用脚本来提取excel表格字符

exp:

from hilbertcurve.hilbertcurve import HilbertCurve
import xlrd
readbook = xlrd.open_workbook('E:\\希尔伯特\\password.xls')
sheet = readbook.sheet_by_index(0)
f = open('E:\\希尔伯特\\base64.txt','w+')
hilbert_curve = HilbertCurve(17, 2)
base64 = ''
for i in range(65536):
    [j,k] = hilbert_curve.point_from_distance(i)
    base64 += sheet.cell(j,k).value
f.write(base64)

运行得到

base64循环解密

解压压缩包得到



      >+++++++++[<+++++++++++++   >-]>+                                               ++[<                         +++++++++++++++++++++++++++++
      ++++++++>-]>++[<+++++++++   +++++                                              ++++++                        +++++++++++++++++++++++++++++
      ++++++++++++>-]>++++[<+++   +++++                                             ++++++++                       +++++++++++++>-]>+++[<+++++++
      +++++                       +++++                                            ++++  ++++                      +++++
      +++++                       +++++                                           +>-]    ++++                     +++++
      +++++                       +++++                                          ++++      ++++                    +++++
      +++++                       +++++                                         ++++        ++++                   +++++
      +++++                       +++++                                        ++++          ++++                  +++++
      +++++                       >>+++                                       +++[            <+++                 +++++
      +++++                       +++++                                      +>-]              >++[                <++++
      +++++++++++++++++++++++++   +++++                                     +++++++>-]>+++++++++++[<               +++++        ++++++>-]>++[<++
      +++++++++++++++++++++++++   +++++                                    ++++++++++++++++++++++++++              +>-]>       +++++++[<++++++++
      +++++++>-]+++++++++++++++   +++++                                   ++++++++++++++++++++++++++++             +++++       +++         +++++
      +++++                       +++++                                  ++++                      ++++            +++++                   +++++
      +++++                       +++++                                 ++++                        >>++           +++[<                   +++++
      +++++                       +++++                                ++++                          >-]>          +++++                   +++[<
      +++++                       +++++                               +>-]                            >+++         +++[<                   +++++
      +++++                       +++++                              ++>-                              ]>++        +++++                   [<+++
      +++++                       +++++                             ++>-                                ]+++       +++++                   +++++
      +++++                       +++++++++++++++++++++++++++      ++++                                  ++++      +++++++++++++++++++++++++++++
      +++++                       ++++++++++++++>>++[<+++++++     ++++                                    ++++     +++++++++++++++++++++++++++++
      +++++                       ++++++++++>-]>+++++[<++++++    ++++                                      ++++    +++++>-]>+++++++[<+++++++>-]>
++++                                                                                                                                              ++++
[<+++                                                                                                                                            +++++
+>-]>+++++[<+++++++++++++++++++>-]>++++[<+++++++++++++>-]>+++++[<+++++++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++[<
++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++[<+++++++++++++++++>-
]>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>+++++++[<+++++++++++++++>-]>+++++++++[<+++++++++++++>-]>++++++[<+++++++++++++++++
>-]>+++[<+++++++++++>-]>+++++[<+++++++++++++++++++>-]>++++++++++[<++++++++++++>-]>++++++[<+++++++++++++++++>-]>+++++++[<+++++++++++++++>-]++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++>-]>+++++[<+++++++++++++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>>+++
+++[<+++++++++++++++++++>-]<.>>++++++[<+++++++++++++++++++>-]<.>>+++[<+++++++++++++++++++++++++++++++++++++>-]<.>>++++++[<+++++++++++++++++++>-]<.>

bk解密

整理得到

1	117,111,122,116,123,83,114,82,114,82,121,118,105,103,95,88,102,105,101,118,95,49,72,95,49,72,95,52,95,101,101,48,109,119,118,105,117,102,33,95,120,102,105,101,118,125,101,114,114,111,114

转ascll

埃特巴什码解密

题型三:二维数组

Threebody

下载附件

stegsolve查看

被嘲讽了。。。

ps放大图片查看

发现像素排列有点规律

010查看像素值

再仔细观察可以发现，如果以4为周期的话相邻像素的数值就差不多了，考虑正常情况下该图片的像素点应该是每4个一组。相当于原始图片是四维的，这里被“降维打击”成了三维。我们这里需要做的，便是对图片进行升维处理。

BMP格式的头部有个biBitCount字节是控制每个像素点所占的比特数，现在为24，也就是3个字节，我们将这个字段改为4个字节对应的32

保存后重新打开图片

stegsolve再一次查看

看到左上角有一些小白点，代表着那里隐藏着一些信息。使用StegSolve的Data Extract功能查看

根据这张照片和“David”的提示，通过一番搜索可得知这一位是知名的数学家大卫·希尔伯特

修改BMP的文件头，使得StegSolve把该通道识别为Alpha通道

exp:

with open('E:\\希尔伯特\\threebody.bmp', 'rb') as f:
    d = f.read()

w = 580
h = 435
b = 4
l = bytearray(d)
off = l[10]
for i in range(h):
    for j in range(w):
        l[off+j*b+i*b*w] = l[off+j*b+i*b*w+3]

with open('E:\\希尔伯特\\threebody_new.bmp', 'wb') as f:
    f.write(l)

运行得到

stegsolve查看

二维数组

搜索希尔伯特与三体看到这个视频

https://www.bilibili.com/video/BV1Sf4y147J9/

把二维的01矩阵降维成一维的二进制流

exp:

import numpy as np
from PIL import Image
from hilbertcurve.hilbertcurve import HilbertCurve

with Image.open('E:\\希尔伯特\\threebody_new.bmp') as img:
    arr = np.asarray(img)
arr = np.vectorize(lambda x: x&1)(arr[:,:,2])

for x1 in range(np.size(arr,0)):
    if sum(arr[x1])>0:
        break
for x2 in reversed(range(np.size(arr,0))):
    if sum(arr[x2])>0:
        break
for y1 in range(np.size(arr,1)):
    if sum(arr[:,y1])>0:
        break
for y2 in reversed(range(np.size(arr,1))):
    if sum(arr[:,y2])>0:
        break

arr = arr[x1:x2+1, y1:y2+1]

hilbert_curve = HilbertCurve(7, 2)

s = ''
for i in range(np.size(arr)):
    [x,y] = hilbert_curve.point_from_distance(i)
    s += str(arr[127-y][x])

with open('E:\\希尔伯特\\output', 'wb') as f:
    f.write(int(s,2).to_bytes(2048, 'big'))

运行得到一段代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* a(char* s);

char t[65536];

void b()
{
	printf("%s\n\nint main()\n{\n\tstrcpy(t, \"%s\");\n\tb();\n\treturn 0;\n}\n\nchar* a(char* s)\n{\n\tint l=strlen(s);\n\tchar* n=malloc(l*2+1);\n\tchar* p=n;\n\tfor(int i=0; i<l; i++)\n\t\tswitch(s[i])\n\t\t{\n\t\t\tcase '\\n':\n\t\t\t\t*p++='\\\\'; *p++='n'; break;\n\t\t\tcase '\\t':\n\t\t\t\t*p++='\\\\'; *p++='t'; break;\n\t\t\tcase '\\\\':\n\t\t\t\t*p++='\\\\'; *p++='\\\\'; break;\n\t\t\tcase '\\\"':\n\t\t\t\t*p++='\\\\'; *p++='\\\"'; break;\n\t\t\tdefault:\n\t\t\t\t*p++=s[i]; break;\n\t\t}\n\t\t*p=0;\n\n\treturn n;\n}\n", t, a(t)); 		  		  		 		   		    	 		  			 				 		 	   	    		   	 		 		 	 	   	 	 		 			   		 	 	 		 	  	  		     		 			  	     	 		 		   	 					 	 	     			  	   		      		 		   		   	 		  	 	 		 		 	 					 	
}

int main()
{
	strcpy(t, "#include <stdio.h>\n#include <string.h>\n#include <stdlib.h>\n\nchar* a(char* s);\n\nchar t[65536];\n\nvoid b()\n{\n\tprintf(\"%s\\n\\nint main()\\n{\\n\\tstrcpy(t, \\\"%s\\\");\\n\\tb();\\n\\treturn 0;\\n}\\n\\nchar* a(char* s)\\n{\\n\\tint l=strlen(s);\\n\\tchar* n=malloc(l*2+1);\\n\\tchar* p=n;\\n\\tfor(int i=0; i<l; i++)\\n\\t\\tswitch(s[i])\\n\\t\\t{\\n\\t\\t\\tcase '\\\\n':\\n\\t\\t\\t\\t*p++='\\\\\\\\'; *p++='n'; break;\\n\\t\\t\\tcase '\\\\t':\\n\\t\\t\\t\\t*p++='\\\\\\\\'; *p++='t'; break;\\n\\t\\t\\tcase '\\\\\\\\':\\n\\t\\t\\t\\t*p++='\\\\\\\\'; *p++='\\\\\\\\'; break;\\n\\t\\t\\tcase '\\\\\\\"':\\n\\t\\t\\t\\t*p++='\\\\\\\\'; *p++='\\\\\\\"'; break;\\n\\t\\t\\tdefault:\\n\\t\\t\\t\\t*p++=s[i]; break;\\n\\t\\t}\\n\\t\\t*p=0;\\n\\n\\treturn n;\\n}\\n\", t, a(t));\n}");
	b();
	return 0;
}

char* a(char* s)
{
	int l=strlen(s);
	char* n=malloc(l*2+1);
	char* p=n;
	for(int i=0; i<l; i++)
		switch(s[i])
		{
			case '\n':
				*p++='\\'; *p++='n'; break;
			case '\t':
				*p++='\\'; *p++='t'; break;
			case '\\':
				*p++='\\'; *p++='\\'; break;
			case '\"':
				*p++='\\'; *p++='\"'; break;
			default:
				*p++=s[i]; break;
		}
		*p=0;

	return n;
}

发现第十一行多出了大片的空白字符，由空格和Tab构成

把空格替换成0、Tab替换成1

exp:

import re
str1=' 		  		  		 		   		    	 		  			 				 		 	   	    		   	 		 		 	 	   	 	 		 			   		 	 	 		 	  	  		     		 			  	     	 		 		   	 					 	 	     			  	   		      		 		   		   	 		  	 	 		 		 	 					 	' #将空格和tab全部复制粘贴过来
#str1=re.sub(' ','',str1)
#str1=re.sub('\[','',str1)
str1=re.sub(' ','0',str1)
str1=re.sub('\t','1',str1)
print(str1)

运行得到

01100110011011000110000101100111011110110100010000110001011011010100010101101110001101010110100100110000011011100100000101101100010111110101000001110010001100000011011000110001011001010110110101111101

二进制转字符串得到flag