Linux 中 crypt 函数的时间复杂度是多少？
What is the time complexity of crypt function in Linux?
在unix中描述如下的crypt函数用于认证：
char *crypt(const char *key, const char *salt);
假设我有key（长度n）和salt（长度m)，调用这个函数的时间复杂度（算法顺序）是多少？
来自 crypt 的手册页：
salt is a two-character string chosen from the set [a-zA-Z0-9./]. This string is used to perturb the algorithm in one of 4096 different ways.
和
By taking the lowest 7 bits of each of the first eight characters of the key, a 56-bit key is obtained.
然后使用如此获得的密钥来加密常量字符串（使用经过调整的 DES 算法），这需要恒定的时间。因此，该函数对于任何有效参数都有常量 运行-time。请注意，此 t运行cating 会导致非常弱的密码。
正如 melpomene, some implementations provide an extension to the crypt function that allow selecting a more secure mode. For the following, I will assume you are using the crypt function from the GNU C library. The manual 所说：
For the MD5-based algorithm, the salt should consist of the string $, followed by up to 8 characters, terminated by either another $ or the end of the string. The result of crypt will be the salt, followed by a $ if the salt didn't end with one, followed by 22 characters from the alphabet ./0-9A-Za-z, up to 34 characters total. Every character in the key is significant.
由于 salt 的长度由常数固定，并且密码哈希函数的时间复杂度与输入的长度呈线性关系，因此 crypt 函数在 key.
中是线性的
我的 glibc 版本也支持更安全的 SHA-256 (selected via $) and SHA-512 (selected via $) cryptographic hash functions in addition to MD5。它们的输入长度也具有线性时间复杂度。
由于我无法理解我现在实际应该做的任务，我已经安排了各种 crypt 方法来支持上述分析。这是结果。
绘制的是 crypt 函数中花费的执行时间与 key 字符串的长度的关系。每个数据系列都覆盖有线性回归，但 DES 除外，在 DES 中绘制的是平均值。我很惊讶 SHA-512 实际上 比 SHA-256 更快。
用于基准测试的代码在此处 (benchmark.c)。
#define _GNU_SOURCE /* crypt */
#include <errno.h> /* errno, strerror */
#include <stdio.h> /* FILE, fopen, fclose, fprintf */
#include <stdlib.h> /* EXIT_{SUCCESS,FAILURE}, malloc, free, [s]rand */
#include <string.h> /* size_t, strlen */
#include <assert.h> /* assert */
#include <time.h> /* CLOCKS_PER_SEC, clock_t, clock */
#include <unistd.h> /* crypt */
/* Barrier to stop the compiler from re-ordering instructions. */
#define COMPILER_BARRIER asm volatile("" ::: "memory")
/* First character in the printable ASCII range. */
static const char ascii_first = ' ';
/* Last character in the printable ASCII range. */
static const char ascii_last = '~';
/*
Benchmark the time it takes to crypt(3) a key of length *keylen* with salt
*salt*. The result is written to the stream *ostr* so its computation cannot
be optimized away.
*/
static clock_t
measure_crypt(const size_t keylen, const char *const salt, FILE *const ostr)
{
char * key;
const char * passwd;
clock_t t1;
clock_t t2;
size_t i;
key = malloc(keylen + 1);
if (key == NULL)
return ((clock_t) -1);
/*
Generate a random key. The randomness is extremely poor; never do this in
cryptographic applications!
*/
for (i = 0; i < keylen; ++i)
key[i] = ascii_first + rand() % (ascii_last - ascii_first);
key[keylen] = '[=10=]';
assert(strlen(key) == keylen);
COMPILER_BARRIER;
t1 = clock();
COMPILER_BARRIER;
passwd = crypt(key, salt);
COMPILER_BARRIER;
t2 = clock();
COMPILER_BARRIER;
fprintf(ostr, "%s\n", passwd);
free(key);
return t2 - t1;
}
/*
The program can be called with zero or one arguments. The argument, if
given, will be used as salt.
*/
int
main(const int argc, const char *const *const argv)
{
const size_t keymax = 2000;
const size_t keystep = 100;
const char * salt = ".."; /* default salt */
FILE * devnull = NULL; /* redirect noise to black hole */
int status = EXIT_SUCCESS;
size_t keylen;
if (argc > 1)
salt = argv[1];
devnull = fopen("/dev/null", "r");
if (devnull == NULL)
goto label_catch;
srand((unsigned) clock());
for (keylen = 0; keylen <= keymax; keylen += keystep)
{
clock_t ticks;
double millis;
ticks= measure_crypt(keylen, salt, devnull);
if (ticks < 0)
goto label_catch;
millis = 1.0E3 * ticks / CLOCKS_PER_SEC;
fprintf(stdout, "%16zu %e\n", keylen, millis);
}
goto label_finally;
label_catch:
status = EXIT_FAILURE;
fprintf(stderr, "error: %s\n", strerror(errno));
label_finally:
if (devnull != NULL)
fclose(devnull);
return status;
}
用于回归和绘图的 Gnuplot 脚本在这里 (plot.gplt)。
set terminal 'svg'
set output 'timings.svg'
set xrange [0 : *]
set yrange [0 : *]
set key top left
set title 'crypt(3) benchmarks'
set xlabel 'key length / bytes'
set ylabel 'computation time / milliseconds'
des(x) = a_des
md5(x) = a_md5 + b_md5 * x
sha256(x) = a_sha256 + b_sha256 * x
sha512(x) = a_sha512 + b_sha512 * x
fit des(x) 'timings.des' via a_des
fit md5(x) 'timings.md5' via a_md5, b_md5
fit sha256(x) 'timings.sha256' via a_sha256, b_sha256
fit sha512(x) 'timings.sha512' via a_sha512, b_sha512
plot des(x) w l notitle lc '#75507b' lt 1 lw 2.5, \
'timings.des' w p t 'DES' lc '#5c3566' pt 7 ps 0.8, \
md5(x) w l notitle lc '#cc0000' lt 1 lw 2.5, \
'timings.md5' w p t 'MD5' lc '#a40000' pt 7 ps 0.8, \
sha256(x) w l notitle lc '#73d216' lt 1 lw 2.5, \
'timings.sha256' w p t 'SHA-256' lc '#4e9a06' pt 7 ps 0.8, \
sha512(x) w l notitle lc '#3465a4' lt 1 lw 2.5, \
'timings.sha512' w p t 'SHA-512' lc '#204a87' pt 7 ps 0.8
最后，Makefile 用于将所有内容连接在一起 (GNUmakefile)。
CC := gcc
CPPFLAGS :=
CFLAGS := -Wall -O2
LDFLAGS :=
LIBS := -lcrypt
all: benchmark timings.svg timings.png
benchmark: benchmark.o
${CC} -o $@ ${CFLAGS} $^ ${LDFLAGS} ${LIBS}
benchmark.o: benchmark.c
${CC} -c ${CPPFLAGS} ${CFLAGS} $<
timings.svg: plot.gplt timings.des timings.md5 timings.sha256 timings.sha512
gnuplot $<
timings.png: timings.svg
convert $< $@
timings.des: benchmark
./$< '$(shell pwgen -ncs 2)' > $@
timings.md5: benchmark
./$< '$$$$(shell pwgen -ncs 8)' > $@
timings.sha256: benchmark
./$< '$$$$(shell pwgen -ncs 16)' > $@
timings.sha512: benchmark
./$< '$$$$(shell pwgen -ncs 16)' > $@
clean:
rm -f benchmark benchmark.o fit.log $(wildcard *.o timings.*)
.PHONY: all clean
在unix中描述如下的crypt函数用于认证：
char *crypt(const char *key, const char *salt);
假设我有key（长度n）和salt（长度m)，调用这个函数的时间复杂度（算法顺序）是多少？
来自 crypt 的手册页：
salt is a two-character string chosen from the set
[a-zA-Z0-9./]. This string is used to perturb the algorithm in one of 4096 different ways.
和
By taking the lowest 7 bits of each of the first eight characters of the key, a 56-bit key is obtained.
然后使用如此获得的密钥来加密常量字符串（使用经过调整的 DES 算法），这需要恒定的时间。因此，该函数对于任何有效参数都有常量 运行-time。请注意，此 t运行cating 会导致非常弱的密码。
正如 melpomene, some implementations provide an extension to the crypt function that allow selecting a more secure mode. For the following, I will assume you are using the crypt function from the GNU C library. The manual 所说：
For the MD5-based algorithm, the salt should consist of the string
$, followed by up to 8 characters, terminated by either another$or the end of the string. The result ofcryptwill be the salt, followed by a$if the salt didn't end with one, followed by 22 characters from the alphabet./0-9A-Za-z, up to 34 characters total. Every character in the key is significant.
由于 salt 的长度由常数固定，并且密码哈希函数的时间复杂度与输入的长度呈线性关系，因此 crypt 函数在 key.
我的 glibc 版本也支持更安全的 SHA-256 (selected via $) and SHA-512 (selected via $) cryptographic hash functions in addition to MD5。它们的输入长度也具有线性时间复杂度。
由于我无法理解我现在实际应该做的任务，我已经安排了各种 crypt 方法来支持上述分析。这是结果。
绘制的是 crypt 函数中花费的执行时间与 key 字符串的长度的关系。每个数据系列都覆盖有线性回归，但 DES 除外，在 DES 中绘制的是平均值。我很惊讶 SHA-512 实际上 比 SHA-256 更快。
用于基准测试的代码在此处 (benchmark.c)。
#define _GNU_SOURCE /* crypt */
#include <errno.h> /* errno, strerror */
#include <stdio.h> /* FILE, fopen, fclose, fprintf */
#include <stdlib.h> /* EXIT_{SUCCESS,FAILURE}, malloc, free, [s]rand */
#include <string.h> /* size_t, strlen */
#include <assert.h> /* assert */
#include <time.h> /* CLOCKS_PER_SEC, clock_t, clock */
#include <unistd.h> /* crypt */
/* Barrier to stop the compiler from re-ordering instructions. */
#define COMPILER_BARRIER asm volatile("" ::: "memory")
/* First character in the printable ASCII range. */
static const char ascii_first = ' ';
/* Last character in the printable ASCII range. */
static const char ascii_last = '~';
/*
Benchmark the time it takes to crypt(3) a key of length *keylen* with salt
*salt*. The result is written to the stream *ostr* so its computation cannot
be optimized away.
*/
static clock_t
measure_crypt(const size_t keylen, const char *const salt, FILE *const ostr)
{
char * key;
const char * passwd;
clock_t t1;
clock_t t2;
size_t i;
key = malloc(keylen + 1);
if (key == NULL)
return ((clock_t) -1);
/*
Generate a random key. The randomness is extremely poor; never do this in
cryptographic applications!
*/
for (i = 0; i < keylen; ++i)
key[i] = ascii_first + rand() % (ascii_last - ascii_first);
key[keylen] = '[=10=]';
assert(strlen(key) == keylen);
COMPILER_BARRIER;
t1 = clock();
COMPILER_BARRIER;
passwd = crypt(key, salt);
COMPILER_BARRIER;
t2 = clock();
COMPILER_BARRIER;
fprintf(ostr, "%s\n", passwd);
free(key);
return t2 - t1;
}
/*
The program can be called with zero or one arguments. The argument, if
given, will be used as salt.
*/
int
main(const int argc, const char *const *const argv)
{
const size_t keymax = 2000;
const size_t keystep = 100;
const char * salt = ".."; /* default salt */
FILE * devnull = NULL; /* redirect noise to black hole */
int status = EXIT_SUCCESS;
size_t keylen;
if (argc > 1)
salt = argv[1];
devnull = fopen("/dev/null", "r");
if (devnull == NULL)
goto label_catch;
srand((unsigned) clock());
for (keylen = 0; keylen <= keymax; keylen += keystep)
{
clock_t ticks;
double millis;
ticks= measure_crypt(keylen, salt, devnull);
if (ticks < 0)
goto label_catch;
millis = 1.0E3 * ticks / CLOCKS_PER_SEC;
fprintf(stdout, "%16zu %e\n", keylen, millis);
}
goto label_finally;
label_catch:
status = EXIT_FAILURE;
fprintf(stderr, "error: %s\n", strerror(errno));
label_finally:
if (devnull != NULL)
fclose(devnull);
return status;
}
用于回归和绘图的 Gnuplot 脚本在这里 (plot.gplt)。
set terminal 'svg'
set output 'timings.svg'
set xrange [0 : *]
set yrange [0 : *]
set key top left
set title 'crypt(3) benchmarks'
set xlabel 'key length / bytes'
set ylabel 'computation time / milliseconds'
des(x) = a_des
md5(x) = a_md5 + b_md5 * x
sha256(x) = a_sha256 + b_sha256 * x
sha512(x) = a_sha512 + b_sha512 * x
fit des(x) 'timings.des' via a_des
fit md5(x) 'timings.md5' via a_md5, b_md5
fit sha256(x) 'timings.sha256' via a_sha256, b_sha256
fit sha512(x) 'timings.sha512' via a_sha512, b_sha512
plot des(x) w l notitle lc '#75507b' lt 1 lw 2.5, \
'timings.des' w p t 'DES' lc '#5c3566' pt 7 ps 0.8, \
md5(x) w l notitle lc '#cc0000' lt 1 lw 2.5, \
'timings.md5' w p t 'MD5' lc '#a40000' pt 7 ps 0.8, \
sha256(x) w l notitle lc '#73d216' lt 1 lw 2.5, \
'timings.sha256' w p t 'SHA-256' lc '#4e9a06' pt 7 ps 0.8, \
sha512(x) w l notitle lc '#3465a4' lt 1 lw 2.5, \
'timings.sha512' w p t 'SHA-512' lc '#204a87' pt 7 ps 0.8
最后，Makefile 用于将所有内容连接在一起 (GNUmakefile)。
CC := gcc
CPPFLAGS :=
CFLAGS := -Wall -O2
LDFLAGS :=
LIBS := -lcrypt
all: benchmark timings.svg timings.png
benchmark: benchmark.o
${CC} -o $@ ${CFLAGS} $^ ${LDFLAGS} ${LIBS}
benchmark.o: benchmark.c
${CC} -c ${CPPFLAGS} ${CFLAGS} $<
timings.svg: plot.gplt timings.des timings.md5 timings.sha256 timings.sha512
gnuplot $<
timings.png: timings.svg
convert $< $@
timings.des: benchmark
./$< '$(shell pwgen -ncs 2)' > $@
timings.md5: benchmark
./$< '$$$$(shell pwgen -ncs 8)' > $@
timings.sha256: benchmark
./$< '$$$$(shell pwgen -ncs 16)' > $@
timings.sha512: benchmark
./$< '$$$$(shell pwgen -ncs 16)' > $@
clean:
rm -f benchmark benchmark.o fit.log $(wildcard *.o timings.*)
.PHONY: all clean